/usr/bin/java -ea -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/AutomizerC.xml -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/prod4br-ll_unwindbound2.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-e106359-m [2022-04-14 17:22:08,204 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-14 17:22:08,206 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-14 17:22:08,249 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-14 17:22:08,249 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-14 17:22:08,251 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-14 17:22:08,253 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-14 17:22:08,255 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-14 17:22:08,257 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-14 17:22:08,261 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-14 17:22:08,261 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-14 17:22:08,263 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-14 17:22:08,263 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-14 17:22:08,265 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-14 17:22:08,266 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-14 17:22:08,268 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-14 17:22:08,269 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-14 17:22:08,269 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-14 17:22:08,271 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-14 17:22:08,276 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-14 17:22:08,278 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-14 17:22:08,279 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-14 17:22:08,280 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-14 17:22:08,280 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-14 17:22:08,282 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-14 17:22:08,287 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-14 17:22:08,287 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-14 17:22:08,287 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-14 17:22:08,288 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-14 17:22:08,288 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-14 17:22:08,290 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-14 17:22:08,290 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-14 17:22:08,291 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-14 17:22:08,292 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-14 17:22:08,292 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-14 17:22:08,293 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-14 17:22:08,293 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-14 17:22:08,294 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-14 17:22:08,294 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-14 17:22:08,294 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-14 17:22:08,294 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-14 17:22:08,296 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-14 17:22:08,296 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf [2022-04-14 17:22:08,324 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-14 17:22:08,325 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-14 17:22:08,325 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-04-14 17:22:08,325 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-04-14 17:22:08,326 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-14 17:22:08,326 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-14 17:22:08,326 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-14 17:22:08,326 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-14 17:22:08,326 INFO L138 SettingsManager]: * Use SBE=true [2022-04-14 17:22:08,327 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-14 17:22:08,327 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-14 17:22:08,328 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-14 17:22:08,328 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-14 17:22:08,328 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-14 17:22:08,328 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-14 17:22:08,328 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-14 17:22:08,328 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-14 17:22:08,328 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-14 17:22:08,328 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-14 17:22:08,329 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-14 17:22:08,330 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-14 17:22:08,330 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-14 17:22:08,330 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-14 17:22:08,330 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-14 17:22:08,330 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-14 17:22:08,330 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-14 17:22:08,330 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-14 17:22:08,331 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-14 17:22:08,331 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-14 17:22:08,331 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-14 17:22:08,331 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2022-04-14 17:22:08,331 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-04-14 17:22:08,332 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-14 17:22:08,332 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-14 17:22:08,553 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-14 17:22:08,574 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-14 17:22:08,576 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-14 17:22:08,577 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-14 17:22:08,578 INFO L275 PluginConnector]: CDTParser initialized [2022-04-14 17:22:08,579 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/prod4br-ll_unwindbound2.c [2022-04-14 17:22:08,640 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8550e4d1d/593577d32e2843ffac95e4741f94ed91/FLAGb30ae5265 [2022-04-14 17:22:08,965 INFO L306 CDTParser]: Found 1 translation units. [2022-04-14 17:22:08,966 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/prod4br-ll_unwindbound2.c [2022-04-14 17:22:08,971 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8550e4d1d/593577d32e2843ffac95e4741f94ed91/FLAGb30ae5265 [2022-04-14 17:22:09,395 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8550e4d1d/593577d32e2843ffac95e4741f94ed91 [2022-04-14 17:22:09,397 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-14 17:22:09,399 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-14 17:22:09,403 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-14 17:22:09,404 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-14 17:22:09,410 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-14 17:22:09,411 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.04 05:22:09" (1/1) ... [2022-04-14 17:22:09,412 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@c131cce and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.04 05:22:09, skipping insertion in model container [2022-04-14 17:22:09,412 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.04 05:22:09" (1/1) ... [2022-04-14 17:22:09,417 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-14 17:22:09,428 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-14 17:22:09,570 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/prod4br-ll_unwindbound2.c[524,537] [2022-04-14 17:22:09,586 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-14 17:22:09,595 INFO L203 MainTranslator]: Completed pre-run [2022-04-14 17:22:09,605 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/prod4br-ll_unwindbound2.c[524,537] [2022-04-14 17:22:09,617 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-14 17:22:09,627 INFO L208 MainTranslator]: Completed translation [2022-04-14 17:22:09,627 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.04 05:22:09 WrapperNode [2022-04-14 17:22:09,628 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-14 17:22:09,628 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-14 17:22:09,628 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-14 17:22:09,629 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-14 17:22:09,639 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.04 05:22:09" (1/1) ... [2022-04-14 17:22:09,639 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.04 05:22:09" (1/1) ... [2022-04-14 17:22:09,655 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.04 05:22:09" (1/1) ... [2022-04-14 17:22:09,655 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.04 05:22:09" (1/1) ... [2022-04-14 17:22:09,662 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.04 05:22:09" (1/1) ... [2022-04-14 17:22:09,665 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.04 05:22:09" (1/1) ... [2022-04-14 17:22:09,666 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.04 05:22:09" (1/1) ... [2022-04-14 17:22:09,668 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-14 17:22:09,668 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-14 17:22:09,668 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-14 17:22:09,668 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-14 17:22:09,669 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.04 05:22:09" (1/1) ... [2022-04-14 17:22:09,686 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-14 17:22:09,694 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-14 17:22:09,702 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-14 17:22:09,703 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-14 17:22:09,727 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-14 17:22:09,727 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-14 17:22:09,727 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-14 17:22:09,727 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-14 17:22:09,727 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-14 17:22:09,727 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-14 17:22:09,727 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-14 17:22:09,727 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-14 17:22:09,728 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-14 17:22:09,728 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-14 17:22:09,728 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-14 17:22:09,728 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-14 17:22:09,728 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-14 17:22:09,728 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-14 17:22:09,728 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-14 17:22:09,728 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-14 17:22:09,728 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-14 17:22:09,728 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-14 17:22:09,728 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-14 17:22:09,729 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-14 17:22:09,777 INFO L234 CfgBuilder]: Building ICFG [2022-04-14 17:22:09,778 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-14 17:22:09,931 INFO L275 CfgBuilder]: Performing block encoding [2022-04-14 17:22:09,937 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-14 17:22:09,937 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-14 17:22:09,938 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.04 05:22:09 BoogieIcfgContainer [2022-04-14 17:22:09,938 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-14 17:22:09,940 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-14 17:22:09,940 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-14 17:22:09,942 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-14 17:22:09,942 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.04 05:22:09" (1/3) ... [2022-04-14 17:22:09,943 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@101fa635 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.04 05:22:09, skipping insertion in model container [2022-04-14 17:22:09,943 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.04 05:22:09" (2/3) ... [2022-04-14 17:22:09,943 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@101fa635 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.04 05:22:09, skipping insertion in model container [2022-04-14 17:22:09,943 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.04 05:22:09" (3/3) ... [2022-04-14 17:22:09,944 INFO L111 eAbstractionObserver]: Analyzing ICFG prod4br-ll_unwindbound2.c [2022-04-14 17:22:09,948 INFO L202 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-14 17:22:09,948 INFO L161 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-14 17:22:10,017 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-14 17:22:10,023 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=PETRI_NET, 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-14 17:22:10,023 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-14 17:22:10,056 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 20 states have (on average 1.45) internal successors, (29), 21 states have internal predecessors, (29), 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-14 17:22:10,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-14 17:22:10,060 INFO L491 BasicCegarLoop]: Found error trace [2022-04-14 17:22:10,061 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-14 17:22:10,061 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-14 17:22:10,073 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-14 17:22:10,075 INFO L85 PathProgramCache]: Analyzing trace with hash 1717894843, now seen corresponding path program 1 times [2022-04-14 17:22:10,084 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-14 17:22:10,085 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1540493563] [2022-04-14 17:22:10,085 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:22:10,086 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-14 17:22:10,203 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:22:10,253 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-14 17:22:10,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:22:10,275 INFO L290 TraceCheckUtils]: 0: Hoare triple {44#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {35#true} is VALID [2022-04-14 17:22:10,275 INFO L290 TraceCheckUtils]: 1: Hoare triple {35#true} assume true; {35#true} is VALID [2022-04-14 17:22:10,275 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {35#true} {35#true} #77#return; {35#true} is VALID [2022-04-14 17:22:10,276 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-14 17:22:10,280 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:22:10,288 INFO L290 TraceCheckUtils]: 0: Hoare triple {35#true} ~cond := #in~cond; {35#true} is VALID [2022-04-14 17:22:10,289 INFO L290 TraceCheckUtils]: 1: Hoare triple {35#true} assume 0 == ~cond;assume false; {36#false} is VALID [2022-04-14 17:22:10,289 INFO L290 TraceCheckUtils]: 2: Hoare triple {36#false} assume true; {36#false} is VALID [2022-04-14 17:22:10,290 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {36#false} {35#true} #69#return; {36#false} is VALID [2022-04-14 17:22:10,291 INFO L272 TraceCheckUtils]: 0: Hoare triple {35#true} call ULTIMATE.init(); {44#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-14 17:22:10,291 INFO L290 TraceCheckUtils]: 1: Hoare triple {44#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {35#true} is VALID [2022-04-14 17:22:10,291 INFO L290 TraceCheckUtils]: 2: Hoare triple {35#true} assume true; {35#true} is VALID [2022-04-14 17:22:10,292 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {35#true} {35#true} #77#return; {35#true} is VALID [2022-04-14 17:22:10,293 INFO L272 TraceCheckUtils]: 4: Hoare triple {35#true} call #t~ret7 := main(); {35#true} is VALID [2022-04-14 17:22:10,293 INFO L290 TraceCheckUtils]: 5: Hoare triple {35#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {35#true} is VALID [2022-04-14 17:22:10,293 INFO L272 TraceCheckUtils]: 6: Hoare triple {35#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {35#true} is VALID [2022-04-14 17:22:10,293 INFO L290 TraceCheckUtils]: 7: Hoare triple {35#true} ~cond := #in~cond; {35#true} is VALID [2022-04-14 17:22:10,294 INFO L290 TraceCheckUtils]: 8: Hoare triple {35#true} assume 0 == ~cond;assume false; {36#false} is VALID [2022-04-14 17:22:10,294 INFO L290 TraceCheckUtils]: 9: Hoare triple {36#false} assume true; {36#false} is VALID [2022-04-14 17:22:10,294 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {36#false} {35#true} #69#return; {36#false} is VALID [2022-04-14 17:22:10,295 INFO L290 TraceCheckUtils]: 11: Hoare triple {36#false} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {36#false} is VALID [2022-04-14 17:22:10,295 INFO L290 TraceCheckUtils]: 12: Hoare triple {36#false} assume !true; {36#false} is VALID [2022-04-14 17:22:10,296 INFO L272 TraceCheckUtils]: 13: Hoare triple {36#false} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {36#false} is VALID [2022-04-14 17:22:10,296 INFO L290 TraceCheckUtils]: 14: Hoare triple {36#false} ~cond := #in~cond; {36#false} is VALID [2022-04-14 17:22:10,297 INFO L290 TraceCheckUtils]: 15: Hoare triple {36#false} assume 0 == ~cond; {36#false} is VALID [2022-04-14 17:22:10,297 INFO L290 TraceCheckUtils]: 16: Hoare triple {36#false} assume !false; {36#false} is VALID [2022-04-14 17:22:10,298 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-14 17:22:10,298 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-14 17:22:10,299 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1540493563] [2022-04-14 17:22:10,300 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1540493563] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-14 17:22:10,300 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-14 17:22:10,300 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-14 17:22:10,303 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1480016008] [2022-04-14 17:22:10,303 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-14 17:22:10,308 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-14 17:22:10,310 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-14 17:22:10,312 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-14 17:22:10,354 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 17 edges. 17 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-14 17:22:10,354 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-14 17:22:10,354 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-14 17:22:10,385 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-14 17:22:10,385 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-14 17:22:10,387 INFO L87 Difference]: Start difference. First operand has 32 states, 20 states have (on average 1.45) internal successors, (29), 21 states have internal predecessors, (29), 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 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-14 17:22:10,574 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:22:10,575 INFO L93 Difference]: Finished difference Result 56 states and 77 transitions. [2022-04-14 17:22:10,576 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-14 17:22:10,576 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-14 17:22:10,577 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-14 17:22:10,578 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-14 17:22:10,586 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 77 transitions. [2022-04-14 17:22:10,587 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-14 17:22:10,592 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 77 transitions. [2022-04-14 17:22:10,592 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 77 transitions. [2022-04-14 17:22:10,695 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 77 edges. 77 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-14 17:22:10,702 INFO L225 Difference]: With dead ends: 56 [2022-04-14 17:22:10,702 INFO L226 Difference]: Without dead ends: 28 [2022-04-14 17:22:10,705 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-14 17:22:10,707 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-14 17:22:10,708 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 40 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-14 17:22:10,724 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2022-04-14 17:22:10,737 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 27. [2022-04-14 17:22:10,738 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-14 17:22:10,738 INFO L82 GeneralOperation]: Start isEquivalent. First operand 28 states. Second operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 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-14 17:22:10,739 INFO L74 IsIncluded]: Start isIncluded. First operand 28 states. Second operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 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-14 17:22:10,739 INFO L87 Difference]: Start difference. First operand 28 states. Second operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 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-14 17:22:10,743 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:22:10,743 INFO L93 Difference]: Finished difference Result 28 states and 34 transitions. [2022-04-14 17:22:10,743 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 34 transitions. [2022-04-14 17:22:10,744 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:22:10,744 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:22:10,745 INFO L74 IsIncluded]: Start isIncluded. First operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 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) Second operand 28 states. [2022-04-14 17:22:10,745 INFO L87 Difference]: Start difference. First operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 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) Second operand 28 states. [2022-04-14 17:22:10,748 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:22:10,748 INFO L93 Difference]: Finished difference Result 28 states and 34 transitions. [2022-04-14 17:22:10,748 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 34 transitions. [2022-04-14 17:22:10,749 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:22:10,749 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:22:10,749 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-14 17:22:10,749 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-14 17:22:10,750 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 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-14 17:22:10,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 33 transitions. [2022-04-14 17:22:10,753 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 33 transitions. Word has length 17 [2022-04-14 17:22:10,753 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-14 17:22:10,753 INFO L478 AbstractCegarLoop]: Abstraction has 27 states and 33 transitions. [2022-04-14 17:22:10,753 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-14 17:22:10,753 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 33 transitions. [2022-04-14 17:22:10,754 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-14 17:22:10,754 INFO L491 BasicCegarLoop]: Found error trace [2022-04-14 17:22:10,754 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-14 17:22:10,754 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-14 17:22:10,755 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-14 17:22:10,759 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-14 17:22:10,759 INFO L85 PathProgramCache]: Analyzing trace with hash 444281082, now seen corresponding path program 1 times [2022-04-14 17:22:10,759 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-14 17:22:10,760 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [875454613] [2022-04-14 17:22:10,760 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:22:10,760 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-14 17:22:10,795 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-14 17:22:10,796 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1946981358] [2022-04-14 17:22:10,796 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:22:10,796 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-14 17:22:10,797 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-14 17:22:10,798 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-14 17:22:10,802 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-14 17:22:10,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:22:10,845 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-14 17:22:10,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:22:10,866 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-14 17:22:11,000 INFO L272 TraceCheckUtils]: 0: Hoare triple {214#true} call ULTIMATE.init(); {214#true} is VALID [2022-04-14 17:22:11,001 INFO L290 TraceCheckUtils]: 1: Hoare triple {214#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {222#(<= ~counter~0 0)} is VALID [2022-04-14 17:22:11,001 INFO L290 TraceCheckUtils]: 2: Hoare triple {222#(<= ~counter~0 0)} assume true; {222#(<= ~counter~0 0)} is VALID [2022-04-14 17:22:11,002 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {222#(<= ~counter~0 0)} {214#true} #77#return; {222#(<= ~counter~0 0)} is VALID [2022-04-14 17:22:11,002 INFO L272 TraceCheckUtils]: 4: Hoare triple {222#(<= ~counter~0 0)} call #t~ret7 := main(); {222#(<= ~counter~0 0)} is VALID [2022-04-14 17:22:11,003 INFO L290 TraceCheckUtils]: 5: Hoare triple {222#(<= ~counter~0 0)} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {222#(<= ~counter~0 0)} is VALID [2022-04-14 17:22:11,003 INFO L272 TraceCheckUtils]: 6: Hoare triple {222#(<= ~counter~0 0)} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {222#(<= ~counter~0 0)} is VALID [2022-04-14 17:22:11,004 INFO L290 TraceCheckUtils]: 7: Hoare triple {222#(<= ~counter~0 0)} ~cond := #in~cond; {222#(<= ~counter~0 0)} is VALID [2022-04-14 17:22:11,004 INFO L290 TraceCheckUtils]: 8: Hoare triple {222#(<= ~counter~0 0)} assume !(0 == ~cond); {222#(<= ~counter~0 0)} is VALID [2022-04-14 17:22:11,005 INFO L290 TraceCheckUtils]: 9: Hoare triple {222#(<= ~counter~0 0)} assume true; {222#(<= ~counter~0 0)} is VALID [2022-04-14 17:22:11,006 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {222#(<= ~counter~0 0)} {222#(<= ~counter~0 0)} #69#return; {222#(<= ~counter~0 0)} is VALID [2022-04-14 17:22:11,006 INFO L290 TraceCheckUtils]: 11: Hoare triple {222#(<= ~counter~0 0)} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {222#(<= ~counter~0 0)} is VALID [2022-04-14 17:22:11,007 INFO L290 TraceCheckUtils]: 12: Hoare triple {222#(<= ~counter~0 0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {256#(<= |main_#t~post6| 0)} is VALID [2022-04-14 17:22:11,007 INFO L290 TraceCheckUtils]: 13: Hoare triple {256#(<= |main_#t~post6| 0)} assume !(#t~post6 < 2);havoc #t~post6; {215#false} is VALID [2022-04-14 17:22:11,007 INFO L272 TraceCheckUtils]: 14: Hoare triple {215#false} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {215#false} is VALID [2022-04-14 17:22:11,008 INFO L290 TraceCheckUtils]: 15: Hoare triple {215#false} ~cond := #in~cond; {215#false} is VALID [2022-04-14 17:22:11,008 INFO L290 TraceCheckUtils]: 16: Hoare triple {215#false} assume 0 == ~cond; {215#false} is VALID [2022-04-14 17:22:11,008 INFO L290 TraceCheckUtils]: 17: Hoare triple {215#false} assume !false; {215#false} is VALID [2022-04-14 17:22:11,008 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-14 17:22:11,008 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-14 17:22:11,009 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-14 17:22:11,009 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [875454613] [2022-04-14 17:22:11,009 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-14 17:22:11,009 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1946981358] [2022-04-14 17:22:11,009 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1946981358] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-14 17:22:11,009 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-14 17:22:11,010 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-14 17:22:11,010 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [467371854] [2022-04-14 17:22:11,010 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-14 17:22:11,011 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2022-04-14 17:22:11,011 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-14 17:22:11,012 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-14 17:22:11,028 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 18 edges. 18 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-14 17:22:11,028 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-14 17:22:11,028 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-14 17:22:11,029 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-14 17:22:11,029 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-14 17:22:11,029 INFO L87 Difference]: Start difference. First operand 27 states and 33 transitions. Second operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-14 17:22:11,120 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:22:11,120 INFO L93 Difference]: Finished difference Result 37 states and 44 transitions. [2022-04-14 17:22:11,120 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-14 17:22:11,120 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2022-04-14 17:22:11,121 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-14 17:22:11,121 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-14 17:22:11,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 44 transitions. [2022-04-14 17:22:11,123 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-14 17:22:11,126 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 44 transitions. [2022-04-14 17:22:11,126 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 4 states and 44 transitions. [2022-04-14 17:22:11,164 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-14 17:22:11,165 INFO L225 Difference]: With dead ends: 37 [2022-04-14 17:22:11,166 INFO L226 Difference]: Without dead ends: 29 [2022-04-14 17:22:11,166 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-14 17:22:11,167 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 0 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-14 17:22:11,168 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 81 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-14 17:22:11,169 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2022-04-14 17:22:11,175 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2022-04-14 17:22:11,175 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-14 17:22:11,176 INFO L82 GeneralOperation]: Start isEquivalent. First operand 29 states. Second operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 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-14 17:22:11,176 INFO L74 IsIncluded]: Start isIncluded. First operand 29 states. Second operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 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-14 17:22:11,177 INFO L87 Difference]: Start difference. First operand 29 states. Second operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 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-14 17:22:11,179 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:22:11,179 INFO L93 Difference]: Finished difference Result 29 states and 35 transitions. [2022-04-14 17:22:11,180 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2022-04-14 17:22:11,180 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:22:11,180 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:22:11,181 INFO L74 IsIncluded]: Start isIncluded. First operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 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) Second operand 29 states. [2022-04-14 17:22:11,181 INFO L87 Difference]: Start difference. First operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 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) Second operand 29 states. [2022-04-14 17:22:11,183 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:22:11,183 INFO L93 Difference]: Finished difference Result 29 states and 35 transitions. [2022-04-14 17:22:11,184 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2022-04-14 17:22:11,184 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:22:11,184 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:22:11,184 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-14 17:22:11,184 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-14 17:22:11,185 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 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-14 17:22:11,186 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 35 transitions. [2022-04-14 17:22:11,186 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 35 transitions. Word has length 18 [2022-04-14 17:22:11,187 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-14 17:22:11,187 INFO L478 AbstractCegarLoop]: Abstraction has 29 states and 35 transitions. [2022-04-14 17:22:11,187 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-14 17:22:11,187 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2022-04-14 17:22:11,188 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-14 17:22:11,188 INFO L491 BasicCegarLoop]: Found error trace [2022-04-14 17:22:11,188 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-14 17:22:11,215 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-14 17:22:11,405 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-14 17:22:11,405 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-14 17:22:11,406 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-14 17:22:11,406 INFO L85 PathProgramCache]: Analyzing trace with hash 446068542, now seen corresponding path program 1 times [2022-04-14 17:22:11,406 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-14 17:22:11,406 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2064536340] [2022-04-14 17:22:11,407 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:22:11,407 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-14 17:22:11,422 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-14 17:22:11,423 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [860122607] [2022-04-14 17:22:11,423 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:22:11,423 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-14 17:22:11,423 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-14 17:22:11,424 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-14 17:22:11,432 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-14 17:22:11,467 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:22:11,468 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 15 conjunts are in the unsatisfiable core [2022-04-14 17:22:11,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:22:11,480 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-14 17:22:11,657 INFO L272 TraceCheckUtils]: 0: Hoare triple {422#true} call ULTIMATE.init(); {422#true} is VALID [2022-04-14 17:22:11,657 INFO L290 TraceCheckUtils]: 1: Hoare triple {422#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {422#true} is VALID [2022-04-14 17:22:11,658 INFO L290 TraceCheckUtils]: 2: Hoare triple {422#true} assume true; {422#true} is VALID [2022-04-14 17:22:11,658 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {422#true} {422#true} #77#return; {422#true} is VALID [2022-04-14 17:22:11,658 INFO L272 TraceCheckUtils]: 4: Hoare triple {422#true} call #t~ret7 := main(); {422#true} is VALID [2022-04-14 17:22:11,658 INFO L290 TraceCheckUtils]: 5: Hoare triple {422#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {422#true} is VALID [2022-04-14 17:22:11,661 INFO L272 TraceCheckUtils]: 6: Hoare triple {422#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {422#true} is VALID [2022-04-14 17:22:11,661 INFO L290 TraceCheckUtils]: 7: Hoare triple {422#true} ~cond := #in~cond; {422#true} is VALID [2022-04-14 17:22:11,662 INFO L290 TraceCheckUtils]: 8: Hoare triple {422#true} assume !(0 == ~cond); {422#true} is VALID [2022-04-14 17:22:11,662 INFO L290 TraceCheckUtils]: 9: Hoare triple {422#true} assume true; {422#true} is VALID [2022-04-14 17:22:11,664 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {422#true} {422#true} #69#return; {422#true} is VALID [2022-04-14 17:22:11,665 INFO L290 TraceCheckUtils]: 11: Hoare triple {422#true} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {460#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-14 17:22:11,665 INFO L290 TraceCheckUtils]: 12: Hoare triple {460#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {460#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-14 17:22:11,666 INFO L290 TraceCheckUtils]: 13: Hoare triple {460#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} assume !!(#t~post6 < 2);havoc #t~post6; {460#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-14 17:22:11,667 INFO L272 TraceCheckUtils]: 14: Hoare triple {460#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {470#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-14 17:22:11,668 INFO L290 TraceCheckUtils]: 15: Hoare triple {470#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {474#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-14 17:22:11,668 INFO L290 TraceCheckUtils]: 16: Hoare triple {474#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {423#false} is VALID [2022-04-14 17:22:11,668 INFO L290 TraceCheckUtils]: 17: Hoare triple {423#false} assume !false; {423#false} is VALID [2022-04-14 17:22:11,669 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-14 17:22:11,669 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-14 17:22:11,669 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-14 17:22:11,669 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2064536340] [2022-04-14 17:22:11,670 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-14 17:22:11,670 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [860122607] [2022-04-14 17:22:11,670 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [860122607] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-14 17:22:11,670 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-14 17:22:11,670 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-14 17:22:11,671 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [172779418] [2022-04-14 17:22:11,671 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-14 17:22:11,671 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-14 17:22:11,672 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-14 17:22:11,672 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-14 17:22:11,688 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 18 edges. 18 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-14 17:22:11,688 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-14 17:22:11,688 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-14 17:22:11,689 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-14 17:22:11,690 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-14 17:22:11,690 INFO L87 Difference]: Start difference. First operand 29 states and 35 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-14 17:22:11,887 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:22:11,887 INFO L93 Difference]: Finished difference Result 42 states and 53 transitions. [2022-04-14 17:22:11,887 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-14 17:22:11,888 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-14 17:22:11,888 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-14 17:22:11,889 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-14 17:22:11,895 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 53 transitions. [2022-04-14 17:22:11,896 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-14 17:22:11,898 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 53 transitions. [2022-04-14 17:22:11,898 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 53 transitions. [2022-04-14 17:22:11,948 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 53 edges. 53 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-14 17:22:11,949 INFO L225 Difference]: With dead ends: 42 [2022-04-14 17:22:11,950 INFO L226 Difference]: Without dead ends: 40 [2022-04-14 17:22:11,950 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-14 17:22:11,951 INFO L913 BasicCegarLoop]: 24 mSDtfsCounter, 9 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-14 17:22:11,951 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 83 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-14 17:22:11,952 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2022-04-14 17:22:11,959 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 34. [2022-04-14 17:22:11,959 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-14 17:22:11,959 INFO L82 GeneralOperation]: Start isEquivalent. First operand 40 states. Second operand has 34 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 24 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-14 17:22:11,960 INFO L74 IsIncluded]: Start isIncluded. First operand 40 states. Second operand has 34 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 24 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-14 17:22:11,960 INFO L87 Difference]: Start difference. First operand 40 states. Second operand has 34 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 24 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-14 17:22:11,962 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:22:11,962 INFO L93 Difference]: Finished difference Result 40 states and 51 transitions. [2022-04-14 17:22:11,963 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 51 transitions. [2022-04-14 17:22:11,963 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:22:11,963 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:22:11,964 INFO L74 IsIncluded]: Start isIncluded. First operand has 34 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 24 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) Second operand 40 states. [2022-04-14 17:22:11,964 INFO L87 Difference]: Start difference. First operand has 34 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 24 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) Second operand 40 states. [2022-04-14 17:22:11,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:22:11,966 INFO L93 Difference]: Finished difference Result 40 states and 51 transitions. [2022-04-14 17:22:11,966 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 51 transitions. [2022-04-14 17:22:11,967 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:22:11,967 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:22:11,967 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-14 17:22:11,967 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-14 17:22:11,968 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 24 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-14 17:22:11,969 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 40 transitions. [2022-04-14 17:22:11,970 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 40 transitions. Word has length 18 [2022-04-14 17:22:11,970 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-14 17:22:11,970 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 40 transitions. [2022-04-14 17:22:11,970 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-14 17:22:11,970 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 40 transitions. [2022-04-14 17:22:11,976 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-14 17:22:11,976 INFO L491 BasicCegarLoop]: Found error trace [2022-04-14 17:22:11,976 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-14 17:22:11,998 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-14 17:22:12,197 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-14 17:22:12,197 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-14 17:22:12,198 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-14 17:22:12,198 INFO L85 PathProgramCache]: Analyzing trace with hash -1308579644, now seen corresponding path program 1 times [2022-04-14 17:22:12,198 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-14 17:22:12,198 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1818261662] [2022-04-14 17:22:12,199 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:22:12,199 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-14 17:22:12,235 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-14 17:22:12,236 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [530461161] [2022-04-14 17:22:12,236 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:22:12,236 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-14 17:22:12,236 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-14 17:22:12,237 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-14 17:22:12,263 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-14 17:22:12,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:22:12,289 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 15 conjunts are in the unsatisfiable core [2022-04-14 17:22:12,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:22:12,304 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-14 17:22:22,792 INFO L272 TraceCheckUtils]: 0: Hoare triple {668#true} call ULTIMATE.init(); {668#true} is VALID [2022-04-14 17:22:22,793 INFO L290 TraceCheckUtils]: 1: Hoare triple {668#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {668#true} is VALID [2022-04-14 17:22:22,793 INFO L290 TraceCheckUtils]: 2: Hoare triple {668#true} assume true; {668#true} is VALID [2022-04-14 17:22:22,793 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {668#true} {668#true} #77#return; {668#true} is VALID [2022-04-14 17:22:22,793 INFO L272 TraceCheckUtils]: 4: Hoare triple {668#true} call #t~ret7 := main(); {668#true} is VALID [2022-04-14 17:22:22,794 INFO L290 TraceCheckUtils]: 5: Hoare triple {668#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {668#true} is VALID [2022-04-14 17:22:22,794 INFO L272 TraceCheckUtils]: 6: Hoare triple {668#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {668#true} is VALID [2022-04-14 17:22:22,794 INFO L290 TraceCheckUtils]: 7: Hoare triple {668#true} ~cond := #in~cond; {694#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-14 17:22:22,795 INFO L290 TraceCheckUtils]: 8: Hoare triple {694#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {698#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-14 17:22:22,795 INFO L290 TraceCheckUtils]: 9: Hoare triple {698#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {698#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-14 17:22:22,796 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {698#(not (= |assume_abort_if_not_#in~cond| 0))} {668#true} #69#return; {705#(<= 1 main_~y~0)} is VALID [2022-04-14 17:22:22,796 INFO L290 TraceCheckUtils]: 11: Hoare triple {705#(<= 1 main_~y~0)} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {709#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} is VALID [2022-04-14 17:22:22,797 INFO L290 TraceCheckUtils]: 12: Hoare triple {709#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {709#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} is VALID [2022-04-14 17:22:22,798 INFO L290 TraceCheckUtils]: 13: Hoare triple {709#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} assume !!(#t~post6 < 2);havoc #t~post6; {709#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} is VALID [2022-04-14 17:22:22,798 INFO L272 TraceCheckUtils]: 14: Hoare triple {709#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {668#true} is VALID [2022-04-14 17:22:22,798 INFO L290 TraceCheckUtils]: 15: Hoare triple {668#true} ~cond := #in~cond; {722#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-14 17:22:22,799 INFO L290 TraceCheckUtils]: 16: Hoare triple {722#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {726#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-14 17:22:22,799 INFO L290 TraceCheckUtils]: 17: Hoare triple {726#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {726#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-14 17:22:24,802 WARN L284 TraceCheckUtils]: 18: Hoare quadruple {726#(not (= |__VERIFIER_assert_#in~cond| 0))} {709#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} #71#return; {733#(and (or (and (= (mod (+ (* main_~y~0 main_~x~0) (* (- 1) main_~q~0)) (* main_~b~0 main_~a~0)) 0) (not (= main_~a~0 0))) (= (+ (* main_~y~0 main_~x~0) (* (- 1) main_~q~0)) 0)) (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} is UNKNOWN [2022-04-14 17:22:24,804 INFO L290 TraceCheckUtils]: 19: Hoare triple {733#(and (or (and (= (mod (+ (* main_~y~0 main_~x~0) (* (- 1) main_~q~0)) (* main_~b~0 main_~a~0)) 0) (not (= main_~a~0 0))) (= (+ (* main_~y~0 main_~x~0) (* (- 1) main_~q~0)) 0)) (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} assume !(0 != ~a~0 && 0 != ~b~0); {737#(and (= main_~q~0 (* main_~y~0 main_~x~0)) (<= 1 main_~y~0))} is VALID [2022-04-14 17:22:24,805 INFO L272 TraceCheckUtils]: 20: Hoare triple {737#(and (= main_~q~0 (* main_~y~0 main_~x~0)) (<= 1 main_~y~0))} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {741#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-14 17:22:24,805 INFO L290 TraceCheckUtils]: 21: Hoare triple {741#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {745#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-14 17:22:24,806 INFO L290 TraceCheckUtils]: 22: Hoare triple {745#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {669#false} is VALID [2022-04-14 17:22:24,806 INFO L290 TraceCheckUtils]: 23: Hoare triple {669#false} assume !false; {669#false} is VALID [2022-04-14 17:22:24,806 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-14 17:22:24,806 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-14 17:23:05,973 INFO L290 TraceCheckUtils]: 23: Hoare triple {669#false} assume !false; {669#false} is VALID [2022-04-14 17:23:05,973 INFO L290 TraceCheckUtils]: 22: Hoare triple {745#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {669#false} is VALID [2022-04-14 17:23:05,974 INFO L290 TraceCheckUtils]: 21: Hoare triple {741#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {745#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-14 17:23:05,975 INFO L272 TraceCheckUtils]: 20: Hoare triple {761#(= main_~q~0 (* main_~y~0 main_~x~0))} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {741#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-14 17:23:05,976 INFO L290 TraceCheckUtils]: 19: Hoare triple {765#(or (= main_~q~0 (* main_~y~0 main_~x~0)) (and (not (= main_~b~0 0)) (not (= main_~a~0 0))))} assume !(0 != ~a~0 && 0 != ~b~0); {761#(= main_~q~0 (* main_~y~0 main_~x~0))} is VALID [2022-04-14 17:23:05,978 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {726#(not (= |__VERIFIER_assert_#in~cond| 0))} {668#true} #71#return; {765#(or (= main_~q~0 (* main_~y~0 main_~x~0)) (and (not (= main_~b~0 0)) (not (= main_~a~0 0))))} is VALID [2022-04-14 17:23:05,978 INFO L290 TraceCheckUtils]: 17: Hoare triple {726#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {726#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-14 17:23:05,979 INFO L290 TraceCheckUtils]: 16: Hoare triple {778#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {726#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-14 17:23:05,980 INFO L290 TraceCheckUtils]: 15: Hoare triple {668#true} ~cond := #in~cond; {778#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-14 17:23:05,980 INFO L272 TraceCheckUtils]: 14: Hoare triple {668#true} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {668#true} is VALID [2022-04-14 17:23:05,980 INFO L290 TraceCheckUtils]: 13: Hoare triple {668#true} assume !!(#t~post6 < 2);havoc #t~post6; {668#true} is VALID [2022-04-14 17:23:05,980 INFO L290 TraceCheckUtils]: 12: Hoare triple {668#true} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {668#true} is VALID [2022-04-14 17:23:05,980 INFO L290 TraceCheckUtils]: 11: Hoare triple {668#true} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {668#true} is VALID [2022-04-14 17:23:05,980 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {668#true} {668#true} #69#return; {668#true} is VALID [2022-04-14 17:23:05,980 INFO L290 TraceCheckUtils]: 9: Hoare triple {668#true} assume true; {668#true} is VALID [2022-04-14 17:23:05,981 INFO L290 TraceCheckUtils]: 8: Hoare triple {668#true} assume !(0 == ~cond); {668#true} is VALID [2022-04-14 17:23:05,981 INFO L290 TraceCheckUtils]: 7: Hoare triple {668#true} ~cond := #in~cond; {668#true} is VALID [2022-04-14 17:23:05,983 INFO L272 TraceCheckUtils]: 6: Hoare triple {668#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {668#true} is VALID [2022-04-14 17:23:05,984 INFO L290 TraceCheckUtils]: 5: Hoare triple {668#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {668#true} is VALID [2022-04-14 17:23:05,985 INFO L272 TraceCheckUtils]: 4: Hoare triple {668#true} call #t~ret7 := main(); {668#true} is VALID [2022-04-14 17:23:05,985 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {668#true} {668#true} #77#return; {668#true} is VALID [2022-04-14 17:23:05,986 INFO L290 TraceCheckUtils]: 2: Hoare triple {668#true} assume true; {668#true} is VALID [2022-04-14 17:23:05,986 INFO L290 TraceCheckUtils]: 1: Hoare triple {668#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {668#true} is VALID [2022-04-14 17:23:05,986 INFO L272 TraceCheckUtils]: 0: Hoare triple {668#true} call ULTIMATE.init(); {668#true} is VALID [2022-04-14 17:23:05,986 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-14 17:23:05,987 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-14 17:23:05,988 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1818261662] [2022-04-14 17:23:05,988 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-14 17:23:05,988 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [530461161] [2022-04-14 17:23:05,988 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [530461161] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-14 17:23:05,988 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-14 17:23:05,988 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 8] total 15 [2022-04-14 17:23:05,988 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [480814981] [2022-04-14 17:23:05,988 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-14 17:23:05,989 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 4 states have call predecessors, (5), 2 states have call successors, (5) Word has length 24 [2022-04-14 17:23:05,990 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-14 17:23:05,990 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 4 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-14 17:23:08,025 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 37 edges. 36 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-14 17:23:08,025 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-04-14 17:23:08,026 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-14 17:23:08,026 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-04-14 17:23:08,026 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2022-04-14 17:23:08,027 INFO L87 Difference]: Start difference. First operand 34 states and 40 transitions. Second operand has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 4 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-14 17:23:10,410 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:23:10,410 INFO L93 Difference]: Finished difference Result 55 states and 72 transitions. [2022-04-14 17:23:10,411 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-14 17:23:10,411 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 4 states have call predecessors, (5), 2 states have call successors, (5) Word has length 24 [2022-04-14 17:23:10,411 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-14 17:23:10,412 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 4 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-14 17:23:10,414 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 69 transitions. [2022-04-14 17:23:10,414 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 4 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-14 17:23:10,417 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 69 transitions. [2022-04-14 17:23:10,417 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 14 states and 69 transitions. [2022-04-14 17:23:12,497 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 69 edges. 68 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-14 17:23:12,499 INFO L225 Difference]: With dead ends: 55 [2022-04-14 17:23:12,499 INFO L226 Difference]: Without dead ends: 53 [2022-04-14 17:23:12,499 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 34 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=71, Invalid=309, Unknown=0, NotChecked=0, Total=380 [2022-04-14 17:23:12,500 INFO L913 BasicCegarLoop]: 20 mSDtfsCounter, 51 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 199 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 230 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 199 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2022-04-14 17:23:12,501 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 123 Invalid, 230 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 199 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2022-04-14 17:23:12,501 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2022-04-14 17:23:12,531 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 39. [2022-04-14 17:23:12,531 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-14 17:23:12,532 INFO L82 GeneralOperation]: Start isEquivalent. First operand 53 states. Second operand has 39 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 4 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-14 17:23:12,535 INFO L74 IsIncluded]: Start isIncluded. First operand 53 states. Second operand has 39 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 4 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-14 17:23:12,536 INFO L87 Difference]: Start difference. First operand 53 states. Second operand has 39 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 4 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-14 17:23:12,547 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:23:12,547 INFO L93 Difference]: Finished difference Result 53 states and 70 transitions. [2022-04-14 17:23:12,547 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 70 transitions. [2022-04-14 17:23:12,550 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:23:12,550 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:23:12,551 INFO L74 IsIncluded]: Start isIncluded. First operand has 39 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 4 states have call predecessors, (6), 6 states have call successors, (6) Second operand 53 states. [2022-04-14 17:23:12,551 INFO L87 Difference]: Start difference. First operand has 39 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 4 states have call predecessors, (6), 6 states have call successors, (6) Second operand 53 states. [2022-04-14 17:23:12,554 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:23:12,554 INFO L93 Difference]: Finished difference Result 53 states and 70 transitions. [2022-04-14 17:23:12,554 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 70 transitions. [2022-04-14 17:23:12,555 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:23:12,555 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:23:12,558 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-14 17:23:12,558 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-14 17:23:12,558 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 4 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-14 17:23:12,559 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 45 transitions. [2022-04-14 17:23:12,560 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 45 transitions. Word has length 24 [2022-04-14 17:23:12,560 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-14 17:23:12,560 INFO L478 AbstractCegarLoop]: Abstraction has 39 states and 45 transitions. [2022-04-14 17:23:12,560 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 4 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-14 17:23:12,560 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 45 transitions. [2022-04-14 17:23:12,561 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-04-14 17:23:12,561 INFO L491 BasicCegarLoop]: Found error trace [2022-04-14 17:23:12,561 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-14 17:23:12,581 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-14 17:23:12,769 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-14 17:23:12,770 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-14 17:23:12,770 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-14 17:23:12,770 INFO L85 PathProgramCache]: Analyzing trace with hash 1797927234, now seen corresponding path program 1 times [2022-04-14 17:23:12,770 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-14 17:23:12,770 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1174125559] [2022-04-14 17:23:12,770 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:23:12,771 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-14 17:23:12,795 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-14 17:23:12,795 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [558229154] [2022-04-14 17:23:12,795 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:23:12,795 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-14 17:23:12,795 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-14 17:23:12,796 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-14 17:23:12,797 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-14 17:23:12,833 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:23:12,834 INFO L263 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-14 17:23:12,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:23:12,843 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-14 17:23:12,976 INFO L272 TraceCheckUtils]: 0: Hoare triple {1077#true} call ULTIMATE.init(); {1077#true} is VALID [2022-04-14 17:23:12,977 INFO L290 TraceCheckUtils]: 1: Hoare triple {1077#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:12,977 INFO L290 TraceCheckUtils]: 2: Hoare triple {1085#(<= ~counter~0 0)} assume true; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:12,978 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1085#(<= ~counter~0 0)} {1077#true} #77#return; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:12,978 INFO L272 TraceCheckUtils]: 4: Hoare triple {1085#(<= ~counter~0 0)} call #t~ret7 := main(); {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:12,979 INFO L290 TraceCheckUtils]: 5: Hoare triple {1085#(<= ~counter~0 0)} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:12,979 INFO L272 TraceCheckUtils]: 6: Hoare triple {1085#(<= ~counter~0 0)} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:12,980 INFO L290 TraceCheckUtils]: 7: Hoare triple {1085#(<= ~counter~0 0)} ~cond := #in~cond; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:12,980 INFO L290 TraceCheckUtils]: 8: Hoare triple {1085#(<= ~counter~0 0)} assume !(0 == ~cond); {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:12,981 INFO L290 TraceCheckUtils]: 9: Hoare triple {1085#(<= ~counter~0 0)} assume true; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:12,982 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1085#(<= ~counter~0 0)} {1085#(<= ~counter~0 0)} #69#return; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:12,982 INFO L290 TraceCheckUtils]: 11: Hoare triple {1085#(<= ~counter~0 0)} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:12,983 INFO L290 TraceCheckUtils]: 12: Hoare triple {1085#(<= ~counter~0 0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:12,983 INFO L290 TraceCheckUtils]: 13: Hoare triple {1119#(<= ~counter~0 1)} assume !!(#t~post6 < 2);havoc #t~post6; {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:12,984 INFO L272 TraceCheckUtils]: 14: Hoare triple {1119#(<= ~counter~0 1)} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:12,985 INFO L290 TraceCheckUtils]: 15: Hoare triple {1119#(<= ~counter~0 1)} ~cond := #in~cond; {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:12,985 INFO L290 TraceCheckUtils]: 16: Hoare triple {1119#(<= ~counter~0 1)} assume !(0 == ~cond); {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:12,985 INFO L290 TraceCheckUtils]: 17: Hoare triple {1119#(<= ~counter~0 1)} assume true; {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:12,986 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {1119#(<= ~counter~0 1)} {1119#(<= ~counter~0 1)} #71#return; {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:12,987 INFO L290 TraceCheckUtils]: 19: Hoare triple {1119#(<= ~counter~0 1)} assume !!(0 != ~a~0 && 0 != ~b~0); {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:12,987 INFO L290 TraceCheckUtils]: 20: Hoare triple {1119#(<= ~counter~0 1)} assume 0 == (if ~a~0 < 0 && 0 != ~a~0 % 2 then ~a~0 % 2 - 2 else ~a~0 % 2) && 0 == (if ~b~0 < 0 && 0 != ~b~0 % 2 then ~b~0 % 2 - 2 else ~b~0 % 2);~a~0 := (if ~a~0 < 0 && 0 != ~a~0 % 2 then 1 + ~a~0 / 2 else ~a~0 / 2);~b~0 := (if ~b~0 < 0 && 0 != ~b~0 % 2 then 1 + ~b~0 / 2 else ~b~0 / 2);~p~0 := 4 * ~p~0; {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:12,988 INFO L290 TraceCheckUtils]: 21: Hoare triple {1119#(<= ~counter~0 1)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1147#(<= |main_#t~post6| 1)} is VALID [2022-04-14 17:23:12,988 INFO L290 TraceCheckUtils]: 22: Hoare triple {1147#(<= |main_#t~post6| 1)} assume !(#t~post6 < 2);havoc #t~post6; {1078#false} is VALID [2022-04-14 17:23:12,988 INFO L272 TraceCheckUtils]: 23: Hoare triple {1078#false} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {1078#false} is VALID [2022-04-14 17:23:12,988 INFO L290 TraceCheckUtils]: 24: Hoare triple {1078#false} ~cond := #in~cond; {1078#false} is VALID [2022-04-14 17:23:12,988 INFO L290 TraceCheckUtils]: 25: Hoare triple {1078#false} assume 0 == ~cond; {1078#false} is VALID [2022-04-14 17:23:12,989 INFO L290 TraceCheckUtils]: 26: Hoare triple {1078#false} assume !false; {1078#false} is VALID [2022-04-14 17:23:12,989 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-14 17:23:12,989 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-14 17:23:13,142 INFO L290 TraceCheckUtils]: 26: Hoare triple {1078#false} assume !false; {1078#false} is VALID [2022-04-14 17:23:13,142 INFO L290 TraceCheckUtils]: 25: Hoare triple {1078#false} assume 0 == ~cond; {1078#false} is VALID [2022-04-14 17:23:13,143 INFO L290 TraceCheckUtils]: 24: Hoare triple {1078#false} ~cond := #in~cond; {1078#false} is VALID [2022-04-14 17:23:13,143 INFO L272 TraceCheckUtils]: 23: Hoare triple {1078#false} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {1078#false} is VALID [2022-04-14 17:23:13,143 INFO L290 TraceCheckUtils]: 22: Hoare triple {1147#(<= |main_#t~post6| 1)} assume !(#t~post6 < 2);havoc #t~post6; {1078#false} is VALID [2022-04-14 17:23:13,144 INFO L290 TraceCheckUtils]: 21: Hoare triple {1119#(<= ~counter~0 1)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1147#(<= |main_#t~post6| 1)} is VALID [2022-04-14 17:23:13,144 INFO L290 TraceCheckUtils]: 20: Hoare triple {1119#(<= ~counter~0 1)} assume 0 == (if ~a~0 < 0 && 0 != ~a~0 % 2 then ~a~0 % 2 - 2 else ~a~0 % 2) && 0 == (if ~b~0 < 0 && 0 != ~b~0 % 2 then ~b~0 % 2 - 2 else ~b~0 % 2);~a~0 := (if ~a~0 < 0 && 0 != ~a~0 % 2 then 1 + ~a~0 / 2 else ~a~0 / 2);~b~0 := (if ~b~0 < 0 && 0 != ~b~0 % 2 then 1 + ~b~0 / 2 else ~b~0 / 2);~p~0 := 4 * ~p~0; {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:13,145 INFO L290 TraceCheckUtils]: 19: Hoare triple {1119#(<= ~counter~0 1)} assume !!(0 != ~a~0 && 0 != ~b~0); {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:13,146 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {1077#true} {1119#(<= ~counter~0 1)} #71#return; {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:13,146 INFO L290 TraceCheckUtils]: 17: Hoare triple {1077#true} assume true; {1077#true} is VALID [2022-04-14 17:23:13,146 INFO L290 TraceCheckUtils]: 16: Hoare triple {1077#true} assume !(0 == ~cond); {1077#true} is VALID [2022-04-14 17:23:13,146 INFO L290 TraceCheckUtils]: 15: Hoare triple {1077#true} ~cond := #in~cond; {1077#true} is VALID [2022-04-14 17:23:13,146 INFO L272 TraceCheckUtils]: 14: Hoare triple {1119#(<= ~counter~0 1)} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {1077#true} is VALID [2022-04-14 17:23:13,146 INFO L290 TraceCheckUtils]: 13: Hoare triple {1119#(<= ~counter~0 1)} assume !!(#t~post6 < 2);havoc #t~post6; {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:13,147 INFO L290 TraceCheckUtils]: 12: Hoare triple {1085#(<= ~counter~0 0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1119#(<= ~counter~0 1)} is VALID [2022-04-14 17:23:13,147 INFO L290 TraceCheckUtils]: 11: Hoare triple {1085#(<= ~counter~0 0)} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:13,148 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1077#true} {1085#(<= ~counter~0 0)} #69#return; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:13,148 INFO L290 TraceCheckUtils]: 9: Hoare triple {1077#true} assume true; {1077#true} is VALID [2022-04-14 17:23:13,148 INFO L290 TraceCheckUtils]: 8: Hoare triple {1077#true} assume !(0 == ~cond); {1077#true} is VALID [2022-04-14 17:23:13,148 INFO L290 TraceCheckUtils]: 7: Hoare triple {1077#true} ~cond := #in~cond; {1077#true} is VALID [2022-04-14 17:23:13,149 INFO L272 TraceCheckUtils]: 6: Hoare triple {1085#(<= ~counter~0 0)} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1077#true} is VALID [2022-04-14 17:23:13,149 INFO L290 TraceCheckUtils]: 5: Hoare triple {1085#(<= ~counter~0 0)} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:13,149 INFO L272 TraceCheckUtils]: 4: Hoare triple {1085#(<= ~counter~0 0)} call #t~ret7 := main(); {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:13,150 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1085#(<= ~counter~0 0)} {1077#true} #77#return; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:13,150 INFO L290 TraceCheckUtils]: 2: Hoare triple {1085#(<= ~counter~0 0)} assume true; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:13,151 INFO L290 TraceCheckUtils]: 1: Hoare triple {1077#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1085#(<= ~counter~0 0)} is VALID [2022-04-14 17:23:13,151 INFO L272 TraceCheckUtils]: 0: Hoare triple {1077#true} call ULTIMATE.init(); {1077#true} is VALID [2022-04-14 17:23:13,151 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-14 17:23:13,151 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-14 17:23:13,151 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1174125559] [2022-04-14 17:23:13,152 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-14 17:23:13,152 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [558229154] [2022-04-14 17:23:13,152 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [558229154] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-14 17:23:13,152 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-14 17:23:13,152 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 5 [2022-04-14 17:23:13,152 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [649594278] [2022-04-14 17:23:13,152 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-14 17:23:13,153 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) Word has length 27 [2022-04-14 17:23:13,153 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-14 17:23:13,153 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-14 17:23:13,183 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 37 edges. 37 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-14 17:23:13,183 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-14 17:23:13,183 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-14 17:23:13,184 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-14 17:23:13,184 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-14 17:23:13,184 INFO L87 Difference]: Start difference. First operand 39 states and 45 transitions. Second operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-14 17:23:13,302 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:23:13,303 INFO L93 Difference]: Finished difference Result 65 states and 75 transitions. [2022-04-14 17:23:13,303 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-14 17:23:13,303 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) Word has length 27 [2022-04-14 17:23:13,303 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-14 17:23:13,303 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-14 17:23:13,305 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 64 transitions. [2022-04-14 17:23:13,305 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-14 17:23:13,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 64 transitions. [2022-04-14 17:23:13,307 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 64 transitions. [2022-04-14 17:23:13,358 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 64 edges. 64 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-14 17:23:13,359 INFO L225 Difference]: With dead ends: 65 [2022-04-14 17:23:13,359 INFO L226 Difference]: Without dead ends: 55 [2022-04-14 17:23:13,360 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 49 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2022-04-14 17:23:13,361 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 17 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 102 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-14 17:23:13,361 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 102 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-14 17:23:13,362 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-04-14 17:23:13,395 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 53. [2022-04-14 17:23:13,395 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-14 17:23:13,396 INFO L82 GeneralOperation]: Start isEquivalent. First operand 55 states. Second operand has 53 states, 36 states have (on average 1.2777777777777777) internal successors, (46), 38 states have internal predecessors, (46), 10 states have call successors, (10), 8 states have call predecessors, (10), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-14 17:23:13,396 INFO L74 IsIncluded]: Start isIncluded. First operand 55 states. Second operand has 53 states, 36 states have (on average 1.2777777777777777) internal successors, (46), 38 states have internal predecessors, (46), 10 states have call successors, (10), 8 states have call predecessors, (10), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-14 17:23:13,396 INFO L87 Difference]: Start difference. First operand 55 states. Second operand has 53 states, 36 states have (on average 1.2777777777777777) internal successors, (46), 38 states have internal predecessors, (46), 10 states have call successors, (10), 8 states have call predecessors, (10), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-14 17:23:13,398 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:23:13,398 INFO L93 Difference]: Finished difference Result 55 states and 64 transitions. [2022-04-14 17:23:13,398 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 64 transitions. [2022-04-14 17:23:13,399 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:23:13,399 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:23:13,399 INFO L74 IsIncluded]: Start isIncluded. First operand has 53 states, 36 states have (on average 1.2777777777777777) internal successors, (46), 38 states have internal predecessors, (46), 10 states have call successors, (10), 8 states have call predecessors, (10), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) Second operand 55 states. [2022-04-14 17:23:13,399 INFO L87 Difference]: Start difference. First operand has 53 states, 36 states have (on average 1.2777777777777777) internal successors, (46), 38 states have internal predecessors, (46), 10 states have call successors, (10), 8 states have call predecessors, (10), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) Second operand 55 states. [2022-04-14 17:23:13,401 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:23:13,401 INFO L93 Difference]: Finished difference Result 55 states and 64 transitions. [2022-04-14 17:23:13,401 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 64 transitions. [2022-04-14 17:23:13,402 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:23:13,402 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:23:13,402 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-14 17:23:13,402 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-14 17:23:13,402 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 36 states have (on average 1.2777777777777777) internal successors, (46), 38 states have internal predecessors, (46), 10 states have call successors, (10), 8 states have call predecessors, (10), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-14 17:23:13,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 63 transitions. [2022-04-14 17:23:13,404 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 63 transitions. Word has length 27 [2022-04-14 17:23:13,404 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-14 17:23:13,404 INFO L478 AbstractCegarLoop]: Abstraction has 53 states and 63 transitions. [2022-04-14 17:23:13,404 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 4 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-14 17:23:13,405 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 63 transitions. [2022-04-14 17:23:13,405 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-04-14 17:23:13,405 INFO L491 BasicCegarLoop]: Found error trace [2022-04-14 17:23:13,405 INFO L499 BasicCegarLoop]: trace histogram [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-14 17:23:13,435 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-14 17:23:13,627 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-14 17:23:13,628 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-14 17:23:13,628 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-14 17:23:13,628 INFO L85 PathProgramCache]: Analyzing trace with hash 1799714694, now seen corresponding path program 1 times [2022-04-14 17:23:13,629 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-14 17:23:13,629 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [719479771] [2022-04-14 17:23:13,629 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:23:13,629 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-14 17:23:13,650 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-14 17:23:13,650 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [568919707] [2022-04-14 17:23:13,651 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:23:13,651 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-14 17:23:13,651 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-14 17:23:13,655 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-14 17:23:13,656 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-14 17:23:13,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:23:13,699 INFO L263 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 34 conjunts are in the unsatisfiable core [2022-04-14 17:23:13,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:23:13,709 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-14 17:23:15,136 INFO L272 TraceCheckUtils]: 0: Hoare triple {1518#true} call ULTIMATE.init(); {1518#true} is VALID [2022-04-14 17:23:15,137 INFO L290 TraceCheckUtils]: 1: Hoare triple {1518#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1518#true} is VALID [2022-04-14 17:23:15,137 INFO L290 TraceCheckUtils]: 2: Hoare triple {1518#true} assume true; {1518#true} is VALID [2022-04-14 17:23:15,137 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1518#true} {1518#true} #77#return; {1518#true} is VALID [2022-04-14 17:23:15,137 INFO L272 TraceCheckUtils]: 4: Hoare triple {1518#true} call #t~ret7 := main(); {1518#true} is VALID [2022-04-14 17:23:15,147 INFO L290 TraceCheckUtils]: 5: Hoare triple {1518#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {1518#true} is VALID [2022-04-14 17:23:15,147 INFO L272 TraceCheckUtils]: 6: Hoare triple {1518#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1518#true} is VALID [2022-04-14 17:23:15,150 INFO L290 TraceCheckUtils]: 7: Hoare triple {1518#true} ~cond := #in~cond; {1544#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-14 17:23:15,150 INFO L290 TraceCheckUtils]: 8: Hoare triple {1544#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {1548#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-14 17:23:15,151 INFO L290 TraceCheckUtils]: 9: Hoare triple {1548#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {1548#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-14 17:23:15,151 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1548#(not (= |assume_abort_if_not_#in~cond| 0))} {1518#true} #69#return; {1555#(<= 1 main_~y~0)} is VALID [2022-04-14 17:23:15,152 INFO L290 TraceCheckUtils]: 11: Hoare triple {1555#(<= 1 main_~y~0)} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {1559#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-14 17:23:15,152 INFO L290 TraceCheckUtils]: 12: Hoare triple {1559#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1559#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-14 17:23:15,153 INFO L290 TraceCheckUtils]: 13: Hoare triple {1559#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} assume !!(#t~post6 < 2);havoc #t~post6; {1559#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-14 17:23:15,153 INFO L272 TraceCheckUtils]: 14: Hoare triple {1559#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {1518#true} is VALID [2022-04-14 17:23:15,153 INFO L290 TraceCheckUtils]: 15: Hoare triple {1518#true} ~cond := #in~cond; {1572#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-14 17:23:15,154 INFO L290 TraceCheckUtils]: 16: Hoare triple {1572#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {1576#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-14 17:23:15,154 INFO L290 TraceCheckUtils]: 17: Hoare triple {1576#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1576#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-14 17:23:15,155 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {1576#(not (= |__VERIFIER_assert_#in~cond| 0))} {1559#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} #71#return; {1559#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-14 17:23:15,156 INFO L290 TraceCheckUtils]: 19: Hoare triple {1559#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} assume !!(0 != ~a~0 && 0 != ~b~0); {1559#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-14 17:23:15,160 INFO L290 TraceCheckUtils]: 20: Hoare triple {1559#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (<= 1 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} assume 0 == (if ~a~0 < 0 && 0 != ~a~0 % 2 then ~a~0 % 2 - 2 else ~a~0 % 2) && 0 == (if ~b~0 < 0 && 0 != ~b~0 % 2 then ~b~0 % 2 - 2 else ~b~0 % 2);~a~0 := (if ~a~0 < 0 && 0 != ~a~0 % 2 then 1 + ~a~0 / 2 else ~a~0 / 2);~b~0 := (if ~b~0 < 0 && 0 != ~b~0 % 2 then 1 + ~b~0 / 2 else ~b~0 / 2);~p~0 := 4 * ~p~0; {1589#(and (= (div main_~y~0 2) main_~b~0) (<= (mod main_~y~0 2) 0) (= main_~q~0 0) (= main_~p~0 4) (= (div main_~x~0 2) main_~a~0) (<= 1 main_~y~0) (= (mod main_~x~0 2) 0))} is VALID [2022-04-14 17:23:15,161 INFO L290 TraceCheckUtils]: 21: Hoare triple {1589#(and (= (div main_~y~0 2) main_~b~0) (<= (mod main_~y~0 2) 0) (= main_~q~0 0) (= main_~p~0 4) (= (div main_~x~0 2) main_~a~0) (<= 1 main_~y~0) (= (mod main_~x~0 2) 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1589#(and (= (div main_~y~0 2) main_~b~0) (<= (mod main_~y~0 2) 0) (= main_~q~0 0) (= main_~p~0 4) (= (div main_~x~0 2) main_~a~0) (<= 1 main_~y~0) (= (mod main_~x~0 2) 0))} is VALID [2022-04-14 17:23:15,162 INFO L290 TraceCheckUtils]: 22: Hoare triple {1589#(and (= (div main_~y~0 2) main_~b~0) (<= (mod main_~y~0 2) 0) (= main_~q~0 0) (= main_~p~0 4) (= (div main_~x~0 2) main_~a~0) (<= 1 main_~y~0) (= (mod main_~x~0 2) 0))} assume !!(#t~post6 < 2);havoc #t~post6; {1589#(and (= (div main_~y~0 2) main_~b~0) (<= (mod main_~y~0 2) 0) (= main_~q~0 0) (= main_~p~0 4) (= (div main_~x~0 2) main_~a~0) (<= 1 main_~y~0) (= (mod main_~x~0 2) 0))} is VALID [2022-04-14 17:23:15,164 INFO L272 TraceCheckUtils]: 23: Hoare triple {1589#(and (= (div main_~y~0 2) main_~b~0) (<= (mod main_~y~0 2) 0) (= main_~q~0 0) (= main_~p~0 4) (= (div main_~x~0 2) main_~a~0) (<= 1 main_~y~0) (= (mod main_~x~0 2) 0))} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {1599#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-14 17:23:15,165 INFO L290 TraceCheckUtils]: 24: Hoare triple {1599#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1603#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-14 17:23:15,165 INFO L290 TraceCheckUtils]: 25: Hoare triple {1603#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1519#false} is VALID [2022-04-14 17:23:15,165 INFO L290 TraceCheckUtils]: 26: Hoare triple {1519#false} assume !false; {1519#false} is VALID [2022-04-14 17:23:15,165 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-14 17:23:15,165 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-14 17:24:31,184 INFO L290 TraceCheckUtils]: 26: Hoare triple {1519#false} assume !false; {1519#false} is VALID [2022-04-14 17:24:31,185 INFO L290 TraceCheckUtils]: 25: Hoare triple {1603#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1519#false} is VALID [2022-04-14 17:24:31,191 INFO L290 TraceCheckUtils]: 24: Hoare triple {1599#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1603#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-14 17:24:31,192 INFO L272 TraceCheckUtils]: 23: Hoare triple {1619#(= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {1599#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-14 17:24:31,193 INFO L290 TraceCheckUtils]: 22: Hoare triple {1619#(= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))} assume !!(#t~post6 < 2);havoc #t~post6; {1619#(= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))} is VALID [2022-04-14 17:24:31,193 INFO L290 TraceCheckUtils]: 21: Hoare triple {1619#(= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1619#(= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))} is VALID [2022-04-14 17:24:31,197 INFO L290 TraceCheckUtils]: 20: Hoare triple {1629#(or (and (or (not (= (mod main_~b~0 2) 0)) (= (+ (* (div main_~b~0 2) (* main_~p~0 4) (div main_~a~0 2)) main_~q~0) (* main_~y~0 main_~x~0))) (or (= (mod main_~b~0 2) 0) (= (+ main_~q~0 (* (+ (div main_~b~0 2) 1) (* main_~p~0 4) (div main_~a~0 2))) (* main_~y~0 main_~x~0)))) (not (= (mod main_~a~0 2) 0)) (and (not (< main_~b~0 0)) (not (<= (mod main_~b~0 2) 0))))} assume 0 == (if ~a~0 < 0 && 0 != ~a~0 % 2 then ~a~0 % 2 - 2 else ~a~0 % 2) && 0 == (if ~b~0 < 0 && 0 != ~b~0 % 2 then ~b~0 % 2 - 2 else ~b~0 % 2);~a~0 := (if ~a~0 < 0 && 0 != ~a~0 % 2 then 1 + ~a~0 / 2 else ~a~0 / 2);~b~0 := (if ~b~0 < 0 && 0 != ~b~0 % 2 then 1 + ~b~0 / 2 else ~b~0 / 2);~p~0 := 4 * ~p~0; {1619#(= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))} is VALID [2022-04-14 17:24:31,198 INFO L290 TraceCheckUtils]: 19: Hoare triple {1629#(or (and (or (not (= (mod main_~b~0 2) 0)) (= (+ (* (div main_~b~0 2) (* main_~p~0 4) (div main_~a~0 2)) main_~q~0) (* main_~y~0 main_~x~0))) (or (= (mod main_~b~0 2) 0) (= (+ main_~q~0 (* (+ (div main_~b~0 2) 1) (* main_~p~0 4) (div main_~a~0 2))) (* main_~y~0 main_~x~0)))) (not (= (mod main_~a~0 2) 0)) (and (not (< main_~b~0 0)) (not (<= (mod main_~b~0 2) 0))))} assume !!(0 != ~a~0 && 0 != ~b~0); {1629#(or (and (or (not (= (mod main_~b~0 2) 0)) (= (+ (* (div main_~b~0 2) (* main_~p~0 4) (div main_~a~0 2)) main_~q~0) (* main_~y~0 main_~x~0))) (or (= (mod main_~b~0 2) 0) (= (+ main_~q~0 (* (+ (div main_~b~0 2) 1) (* main_~p~0 4) (div main_~a~0 2))) (* main_~y~0 main_~x~0)))) (not (= (mod main_~a~0 2) 0)) (and (not (< main_~b~0 0)) (not (<= (mod main_~b~0 2) 0))))} is VALID [2022-04-14 17:24:31,205 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {1576#(not (= |__VERIFIER_assert_#in~cond| 0))} {1636#(or (not (= (mod main_~a~0 2) 0)) (= (mod main_~b~0 2) 0) (not (< main_~b~0 0)) (not (= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))) (= (+ main_~q~0 (* (+ (div main_~b~0 2) 1) (* main_~p~0 4) (div main_~a~0 2))) (* main_~y~0 main_~x~0)))} #71#return; {1629#(or (and (or (not (= (mod main_~b~0 2) 0)) (= (+ (* (div main_~b~0 2) (* main_~p~0 4) (div main_~a~0 2)) main_~q~0) (* main_~y~0 main_~x~0))) (or (= (mod main_~b~0 2) 0) (= (+ main_~q~0 (* (+ (div main_~b~0 2) 1) (* main_~p~0 4) (div main_~a~0 2))) (* main_~y~0 main_~x~0)))) (not (= (mod main_~a~0 2) 0)) (and (not (< main_~b~0 0)) (not (<= (mod main_~b~0 2) 0))))} is VALID [2022-04-14 17:24:31,206 INFO L290 TraceCheckUtils]: 17: Hoare triple {1576#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1576#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-14 17:24:31,209 INFO L290 TraceCheckUtils]: 16: Hoare triple {1646#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {1576#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-14 17:24:31,209 INFO L290 TraceCheckUtils]: 15: Hoare triple {1518#true} ~cond := #in~cond; {1646#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-14 17:24:31,209 INFO L272 TraceCheckUtils]: 14: Hoare triple {1636#(or (not (= (mod main_~a~0 2) 0)) (= (mod main_~b~0 2) 0) (not (< main_~b~0 0)) (not (= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))) (= (+ main_~q~0 (* (+ (div main_~b~0 2) 1) (* main_~p~0 4) (div main_~a~0 2))) (* main_~y~0 main_~x~0)))} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {1518#true} is VALID [2022-04-14 17:24:31,215 INFO L290 TraceCheckUtils]: 13: Hoare triple {1636#(or (not (= (mod main_~a~0 2) 0)) (= (mod main_~b~0 2) 0) (not (< main_~b~0 0)) (not (= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))) (= (+ main_~q~0 (* (+ (div main_~b~0 2) 1) (* main_~p~0 4) (div main_~a~0 2))) (* main_~y~0 main_~x~0)))} assume !!(#t~post6 < 2);havoc #t~post6; {1636#(or (not (= (mod main_~a~0 2) 0)) (= (mod main_~b~0 2) 0) (not (< main_~b~0 0)) (not (= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))) (= (+ main_~q~0 (* (+ (div main_~b~0 2) 1) (* main_~p~0 4) (div main_~a~0 2))) (* main_~y~0 main_~x~0)))} is VALID [2022-04-14 17:24:31,216 INFO L290 TraceCheckUtils]: 12: Hoare triple {1636#(or (not (= (mod main_~a~0 2) 0)) (= (mod main_~b~0 2) 0) (not (< main_~b~0 0)) (not (= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))) (= (+ main_~q~0 (* (+ (div main_~b~0 2) 1) (* main_~p~0 4) (div main_~a~0 2))) (* main_~y~0 main_~x~0)))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1636#(or (not (= (mod main_~a~0 2) 0)) (= (mod main_~b~0 2) 0) (not (< main_~b~0 0)) (not (= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))) (= (+ main_~q~0 (* (+ (div main_~b~0 2) 1) (* main_~p~0 4) (div main_~a~0 2))) (* main_~y~0 main_~x~0)))} is VALID [2022-04-14 17:24:31,217 INFO L290 TraceCheckUtils]: 11: Hoare triple {1659#(or (<= 0 main_~y~0) (= (mod main_~y~0 2) 0) (= (+ (* (div main_~x~0 2) 4) (* (* (div main_~x~0 2) (div main_~y~0 2)) 4)) (* main_~y~0 main_~x~0)) (not (= (mod main_~x~0 2) 0)))} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {1636#(or (not (= (mod main_~a~0 2) 0)) (= (mod main_~b~0 2) 0) (not (< main_~b~0 0)) (not (= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))) (= (+ main_~q~0 (* (+ (div main_~b~0 2) 1) (* main_~p~0 4) (div main_~a~0 2))) (* main_~y~0 main_~x~0)))} is VALID [2022-04-14 17:24:31,218 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1548#(not (= |assume_abort_if_not_#in~cond| 0))} {1518#true} #69#return; {1659#(or (<= 0 main_~y~0) (= (mod main_~y~0 2) 0) (= (+ (* (div main_~x~0 2) 4) (* (* (div main_~x~0 2) (div main_~y~0 2)) 4)) (* main_~y~0 main_~x~0)) (not (= (mod main_~x~0 2) 0)))} is VALID [2022-04-14 17:24:31,219 INFO L290 TraceCheckUtils]: 9: Hoare triple {1548#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {1548#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-14 17:24:31,219 INFO L290 TraceCheckUtils]: 8: Hoare triple {1672#(or (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond 0))} assume !(0 == ~cond); {1548#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-14 17:24:31,220 INFO L290 TraceCheckUtils]: 7: Hoare triple {1518#true} ~cond := #in~cond; {1672#(or (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond 0))} is VALID [2022-04-14 17:24:31,220 INFO L272 TraceCheckUtils]: 6: Hoare triple {1518#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1518#true} is VALID [2022-04-14 17:24:31,221 INFO L290 TraceCheckUtils]: 5: Hoare triple {1518#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {1518#true} is VALID [2022-04-14 17:24:31,221 INFO L272 TraceCheckUtils]: 4: Hoare triple {1518#true} call #t~ret7 := main(); {1518#true} is VALID [2022-04-14 17:24:31,221 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1518#true} {1518#true} #77#return; {1518#true} is VALID [2022-04-14 17:24:31,221 INFO L290 TraceCheckUtils]: 2: Hoare triple {1518#true} assume true; {1518#true} is VALID [2022-04-14 17:24:31,221 INFO L290 TraceCheckUtils]: 1: Hoare triple {1518#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1518#true} is VALID [2022-04-14 17:24:31,221 INFO L272 TraceCheckUtils]: 0: Hoare triple {1518#true} call ULTIMATE.init(); {1518#true} is VALID [2022-04-14 17:24:31,221 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-14 17:24:31,222 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-14 17:24:31,222 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [719479771] [2022-04-14 17:24:31,222 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-14 17:24:31,222 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [568919707] [2022-04-14 17:24:31,222 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [568919707] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-14 17:24:31,222 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-14 17:24:31,222 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12] total 17 [2022-04-14 17:24:31,222 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1443025126] [2022-04-14 17:24:31,222 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-14 17:24:31,223 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.7647058823529411) internal successors, (30), 14 states have internal predecessors, (30), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 3 states have call successors, (5) Word has length 27 [2022-04-14 17:24:31,225 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-14 17:24:31,225 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 17 states, 17 states have (on average 1.7647058823529411) internal successors, (30), 14 states have internal predecessors, (30), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-14 17:24:31,281 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 42 edges. 42 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-14 17:24:31,281 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-04-14 17:24:31,281 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-14 17:24:31,282 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-04-14 17:24:31,282 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=223, Unknown=0, NotChecked=0, Total=272 [2022-04-14 17:24:31,282 INFO L87 Difference]: Start difference. First operand 53 states and 63 transitions. Second operand has 17 states, 17 states have (on average 1.7647058823529411) internal successors, (30), 14 states have internal predecessors, (30), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-14 17:24:34,685 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:24:34,685 INFO L93 Difference]: Finished difference Result 76 states and 98 transitions. [2022-04-14 17:24:34,685 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-14 17:24:34,685 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.7647058823529411) internal successors, (30), 14 states have internal predecessors, (30), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 3 states have call successors, (5) Word has length 27 [2022-04-14 17:24:34,686 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-14 17:24:34,686 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 17 states have (on average 1.7647058823529411) internal successors, (30), 14 states have internal predecessors, (30), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-14 17:24:34,689 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 83 transitions. [2022-04-14 17:24:34,690 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 17 states have (on average 1.7647058823529411) internal successors, (30), 14 states have internal predecessors, (30), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-14 17:24:34,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 83 transitions. [2022-04-14 17:24:34,692 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 13 states and 83 transitions. [2022-04-14 17:24:34,900 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 83 edges. 83 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-14 17:24:34,902 INFO L225 Difference]: With dead ends: 76 [2022-04-14 17:24:34,902 INFO L226 Difference]: Without dead ends: 74 [2022-04-14 17:24:34,902 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 37 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=84, Invalid=378, Unknown=0, NotChecked=0, Total=462 [2022-04-14 17:24:34,903 INFO L913 BasicCegarLoop]: 23 mSDtfsCounter, 85 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 384 mSolverCounterSat, 83 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 88 SdHoareTripleChecker+Valid, 185 SdHoareTripleChecker+Invalid, 467 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 83 IncrementalHoareTripleChecker+Valid, 384 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2022-04-14 17:24:34,903 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [88 Valid, 185 Invalid, 467 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [83 Valid, 384 Invalid, 0 Unknown, 0 Unchecked, 1.6s Time] [2022-04-14 17:24:34,904 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2022-04-14 17:24:34,936 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 57. [2022-04-14 17:24:34,936 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-14 17:24:34,936 INFO L82 GeneralOperation]: Start isEquivalent. First operand 74 states. Second operand has 57 states, 39 states have (on average 1.2564102564102564) internal successors, (49), 41 states have internal predecessors, (49), 10 states have call successors, (10), 9 states have call predecessors, (10), 7 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-14 17:24:34,937 INFO L74 IsIncluded]: Start isIncluded. First operand 74 states. Second operand has 57 states, 39 states have (on average 1.2564102564102564) internal successors, (49), 41 states have internal predecessors, (49), 10 states have call successors, (10), 9 states have call predecessors, (10), 7 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-14 17:24:34,937 INFO L87 Difference]: Start difference. First operand 74 states. Second operand has 57 states, 39 states have (on average 1.2564102564102564) internal successors, (49), 41 states have internal predecessors, (49), 10 states have call successors, (10), 9 states have call predecessors, (10), 7 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-14 17:24:34,940 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:24:34,940 INFO L93 Difference]: Finished difference Result 74 states and 96 transitions. [2022-04-14 17:24:34,940 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 96 transitions. [2022-04-14 17:24:34,941 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:24:34,941 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:24:34,941 INFO L74 IsIncluded]: Start isIncluded. First operand has 57 states, 39 states have (on average 1.2564102564102564) internal successors, (49), 41 states have internal predecessors, (49), 10 states have call successors, (10), 9 states have call predecessors, (10), 7 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) Second operand 74 states. [2022-04-14 17:24:34,941 INFO L87 Difference]: Start difference. First operand has 57 states, 39 states have (on average 1.2564102564102564) internal successors, (49), 41 states have internal predecessors, (49), 10 states have call successors, (10), 9 states have call predecessors, (10), 7 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) Second operand 74 states. [2022-04-14 17:24:34,944 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:24:34,944 INFO L93 Difference]: Finished difference Result 74 states and 96 transitions. [2022-04-14 17:24:34,944 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 96 transitions. [2022-04-14 17:24:34,944 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:24:34,945 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:24:34,945 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-14 17:24:34,945 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-14 17:24:34,945 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 39 states have (on average 1.2564102564102564) internal successors, (49), 41 states have internal predecessors, (49), 10 states have call successors, (10), 9 states have call predecessors, (10), 7 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-14 17:24:34,946 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 66 transitions. [2022-04-14 17:24:34,947 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 66 transitions. Word has length 27 [2022-04-14 17:24:34,947 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-14 17:24:34,947 INFO L478 AbstractCegarLoop]: Abstraction has 57 states and 66 transitions. [2022-04-14 17:24:34,947 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.7647058823529411) internal successors, (30), 14 states have internal predecessors, (30), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-14 17:24:34,947 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 66 transitions. [2022-04-14 17:24:34,948 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-04-14 17:24:34,948 INFO L491 BasicCegarLoop]: Found error trace [2022-04-14 17:24:34,948 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-14 17:24:34,968 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-04-14 17:24:35,159 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-14 17:24:35,160 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-14 17:24:35,160 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-14 17:24:35,160 INFO L85 PathProgramCache]: Analyzing trace with hash -1613968938, now seen corresponding path program 1 times [2022-04-14 17:24:35,160 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-14 17:24:35,160 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1802408412] [2022-04-14 17:24:35,160 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:24:35,160 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-14 17:24:35,175 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-14 17:24:35,175 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [21978982] [2022-04-14 17:24:35,175 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:24:35,175 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-14 17:24:35,175 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-14 17:24:35,178 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-14 17:24:35,178 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-14 17:24:35,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:24:35,217 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 10 conjunts are in the unsatisfiable core [2022-04-14 17:24:35,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-14 17:24:35,228 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-14 17:24:35,391 INFO L272 TraceCheckUtils]: 0: Hoare triple {2038#true} call ULTIMATE.init(); {2038#true} is VALID [2022-04-14 17:24:35,392 INFO L290 TraceCheckUtils]: 1: Hoare triple {2038#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2038#true} is VALID [2022-04-14 17:24:35,392 INFO L290 TraceCheckUtils]: 2: Hoare triple {2038#true} assume true; {2038#true} is VALID [2022-04-14 17:24:35,392 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2038#true} {2038#true} #77#return; {2038#true} is VALID [2022-04-14 17:24:35,392 INFO L272 TraceCheckUtils]: 4: Hoare triple {2038#true} call #t~ret7 := main(); {2038#true} is VALID [2022-04-14 17:24:35,392 INFO L290 TraceCheckUtils]: 5: Hoare triple {2038#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {2038#true} is VALID [2022-04-14 17:24:35,392 INFO L272 TraceCheckUtils]: 6: Hoare triple {2038#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {2038#true} is VALID [2022-04-14 17:24:35,393 INFO L290 TraceCheckUtils]: 7: Hoare triple {2038#true} ~cond := #in~cond; {2064#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-14 17:24:35,393 INFO L290 TraceCheckUtils]: 8: Hoare triple {2064#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {2068#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-14 17:24:35,394 INFO L290 TraceCheckUtils]: 9: Hoare triple {2068#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {2068#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-14 17:24:35,394 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2068#(not (= |assume_abort_if_not_#in~cond| 0))} {2038#true} #69#return; {2075#(<= 1 main_~y~0)} is VALID [2022-04-14 17:24:35,395 INFO L290 TraceCheckUtils]: 11: Hoare triple {2075#(<= 1 main_~y~0)} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {2079#(<= 1 main_~b~0)} is VALID [2022-04-14 17:24:35,395 INFO L290 TraceCheckUtils]: 12: Hoare triple {2079#(<= 1 main_~b~0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2079#(<= 1 main_~b~0)} is VALID [2022-04-14 17:24:35,396 INFO L290 TraceCheckUtils]: 13: Hoare triple {2079#(<= 1 main_~b~0)} assume !!(#t~post6 < 2);havoc #t~post6; {2079#(<= 1 main_~b~0)} is VALID [2022-04-14 17:24:35,396 INFO L272 TraceCheckUtils]: 14: Hoare triple {2079#(<= 1 main_~b~0)} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {2038#true} is VALID [2022-04-14 17:24:35,396 INFO L290 TraceCheckUtils]: 15: Hoare triple {2038#true} ~cond := #in~cond; {2038#true} is VALID [2022-04-14 17:24:35,396 INFO L290 TraceCheckUtils]: 16: Hoare triple {2038#true} assume !(0 == ~cond); {2038#true} is VALID [2022-04-14 17:24:35,396 INFO L290 TraceCheckUtils]: 17: Hoare triple {2038#true} assume true; {2038#true} is VALID [2022-04-14 17:24:35,397 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {2038#true} {2079#(<= 1 main_~b~0)} #71#return; {2079#(<= 1 main_~b~0)} is VALID [2022-04-14 17:24:35,397 INFO L290 TraceCheckUtils]: 19: Hoare triple {2079#(<= 1 main_~b~0)} assume !(0 != ~a~0 && 0 != ~b~0); {2104#(and (= main_~a~0 0) (<= 1 main_~b~0))} is VALID [2022-04-14 17:24:35,397 INFO L272 TraceCheckUtils]: 20: Hoare triple {2104#(and (= main_~a~0 0) (<= 1 main_~b~0))} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {2038#true} is VALID [2022-04-14 17:24:35,397 INFO L290 TraceCheckUtils]: 21: Hoare triple {2038#true} ~cond := #in~cond; {2038#true} is VALID [2022-04-14 17:24:35,397 INFO L290 TraceCheckUtils]: 22: Hoare triple {2038#true} assume !(0 == ~cond); {2038#true} is VALID [2022-04-14 17:24:35,398 INFO L290 TraceCheckUtils]: 23: Hoare triple {2038#true} assume true; {2038#true} is VALID [2022-04-14 17:24:35,398 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {2038#true} {2104#(and (= main_~a~0 0) (<= 1 main_~b~0))} #73#return; {2104#(and (= main_~a~0 0) (<= 1 main_~b~0))} is VALID [2022-04-14 17:24:35,399 INFO L272 TraceCheckUtils]: 25: Hoare triple {2104#(and (= main_~a~0 0) (<= 1 main_~b~0))} call __VERIFIER_assert((if 0 == ~a~0 * ~b~0 then 1 else 0)); {2123#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-14 17:24:35,399 INFO L290 TraceCheckUtils]: 26: Hoare triple {2123#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {2127#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-14 17:24:35,400 INFO L290 TraceCheckUtils]: 27: Hoare triple {2127#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {2039#false} is VALID [2022-04-14 17:24:35,400 INFO L290 TraceCheckUtils]: 28: Hoare triple {2039#false} assume !false; {2039#false} is VALID [2022-04-14 17:24:35,400 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-14 17:24:35,400 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-14 17:24:35,400 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-14 17:24:35,400 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1802408412] [2022-04-14 17:24:35,401 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-14 17:24:35,401 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [21978982] [2022-04-14 17:24:35,401 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [21978982] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-14 17:24:35,401 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-14 17:24:35,401 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-14 17:24:35,401 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [106257229] [2022-04-14 17:24:35,401 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-14 17:24:35,402 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 29 [2022-04-14 17:24:35,402 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-14 17:24:35,402 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-14 17:24:35,424 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 26 edges. 26 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-14 17:24:35,424 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-14 17:24:35,424 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-14 17:24:35,425 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-14 17:24:35,425 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2022-04-14 17:24:35,425 INFO L87 Difference]: Start difference. First operand 57 states and 66 transitions. Second operand has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-14 17:24:35,816 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:24:35,816 INFO L93 Difference]: Finished difference Result 76 states and 92 transitions. [2022-04-14 17:24:35,817 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-14 17:24:35,817 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 29 [2022-04-14 17:24:35,817 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-14 17:24:35,817 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-14 17:24:35,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 57 transitions. [2022-04-14 17:24:35,819 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-14 17:24:35,820 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 57 transitions. [2022-04-14 17:24:35,820 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 9 states and 57 transitions. [2022-04-14 17:24:35,867 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 57 edges. 57 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-14 17:24:35,868 INFO L225 Difference]: With dead ends: 76 [2022-04-14 17:24:35,868 INFO L226 Difference]: Without dead ends: 60 [2022-04-14 17:24:35,869 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2022-04-14 17:24:35,870 INFO L913 BasicCegarLoop]: 26 mSDtfsCounter, 33 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 110 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 119 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 110 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-14 17:24:35,870 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 141 Invalid, 119 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 110 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-14 17:24:35,870 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2022-04-14 17:24:35,905 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 57. [2022-04-14 17:24:35,905 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-14 17:24:35,905 INFO L82 GeneralOperation]: Start isEquivalent. First operand 60 states. Second operand has 57 states, 41 states have (on average 1.2926829268292683) internal successors, (53), 43 states have internal predecessors, (53), 9 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-14 17:24:35,905 INFO L74 IsIncluded]: Start isIncluded. First operand 60 states. Second operand has 57 states, 41 states have (on average 1.2926829268292683) internal successors, (53), 43 states have internal predecessors, (53), 9 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-14 17:24:35,906 INFO L87 Difference]: Start difference. First operand 60 states. Second operand has 57 states, 41 states have (on average 1.2926829268292683) internal successors, (53), 43 states have internal predecessors, (53), 9 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-14 17:24:35,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:24:35,908 INFO L93 Difference]: Finished difference Result 60 states and 74 transitions. [2022-04-14 17:24:35,908 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 74 transitions. [2022-04-14 17:24:35,908 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:24:35,908 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:24:35,909 INFO L74 IsIncluded]: Start isIncluded. First operand has 57 states, 41 states have (on average 1.2926829268292683) internal successors, (53), 43 states have internal predecessors, (53), 9 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) Second operand 60 states. [2022-04-14 17:24:35,909 INFO L87 Difference]: Start difference. First operand has 57 states, 41 states have (on average 1.2926829268292683) internal successors, (53), 43 states have internal predecessors, (53), 9 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) Second operand 60 states. [2022-04-14 17:24:35,911 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-14 17:24:35,911 INFO L93 Difference]: Finished difference Result 60 states and 74 transitions. [2022-04-14 17:24:35,911 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 74 transitions. [2022-04-14 17:24:35,911 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-14 17:24:35,911 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-14 17:24:35,911 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-14 17:24:35,911 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-14 17:24:35,912 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 41 states have (on average 1.2926829268292683) internal successors, (53), 43 states have internal predecessors, (53), 9 states have call successors, (9), 7 states have call predecessors, (9), 6 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-14 17:24:35,913 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 69 transitions. [2022-04-14 17:24:35,913 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 69 transitions. Word has length 29 [2022-04-14 17:24:35,914 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-14 17:24:35,914 INFO L478 AbstractCegarLoop]: Abstraction has 57 states and 69 transitions. [2022-04-14 17:24:35,914 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-14 17:24:35,914 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 69 transitions. [2022-04-14 17:24:35,915 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-14 17:24:35,915 INFO L491 BasicCegarLoop]: Found error trace [2022-04-14 17:24:35,915 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-14 17:24:35,938 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-14 17:24:36,130 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-14 17:24:36,130 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-14 17:24:36,131 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-14 17:24:36,131 INFO L85 PathProgramCache]: Analyzing trace with hash 604176890, now seen corresponding path program 2 times [2022-04-14 17:24:36,131 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-14 17:24:36,131 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1300998480] [2022-04-14 17:24:36,131 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-14 17:24:36,131 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-14 17:24:36,143 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-14 17:24:36,143 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [849055886] [2022-04-14 17:24:36,143 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-14 17:24:36,143 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-14 17:24:36,143 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-14 17:24:36,144 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-14 17:24:36,162 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-14 17:24:36,197 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-14 17:24:36,197 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2022-04-14 17:24:36,197 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-04-14 17:24:36,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-04-14 17:24:36,230 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-04-14 17:24:36,230 INFO L618 BasicCegarLoop]: Counterexample is feasible [2022-04-14 17:24:36,231 INFO L788 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-14 17:24:36,258 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-14 17:24:36,432 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-14 17:24:36,436 INFO L719 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1, 1, 1, 1] [2022-04-14 17:24:36,438 INFO L177 ceAbstractionStarter]: Computing trace abstraction results [2022-04-14 17:24:36,461 WARN L170 areAnnotationChecker]: reach_errorENTRY has no Hoare annotation [2022-04-14 17:24:36,461 WARN L170 areAnnotationChecker]: ULTIMATE.initENTRY has no Hoare annotation [2022-04-14 17:24:36,461 WARN L170 areAnnotationChecker]: ULTIMATE.startENTRY has no Hoare annotation [2022-04-14 17:24:36,461 WARN L170 areAnnotationChecker]: ULTIMATE.startENTRY has no Hoare annotation [2022-04-14 17:24:36,461 WARN L170 areAnnotationChecker]: assume_abort_if_notENTRY has no Hoare annotation [2022-04-14 17:24:36,461 WARN L170 areAnnotationChecker]: mainENTRY has no Hoare annotation [2022-04-14 17:24:36,461 WARN L170 areAnnotationChecker]: __VERIFIER_assertENTRY has no Hoare annotation [2022-04-14 17:24:36,461 WARN L170 areAnnotationChecker]: reach_errorFINAL has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: ULTIMATE.initFINAL has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L-1 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L-1 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L9 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L9 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L26 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L26 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L12 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L12 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: ULTIMATE.initEXIT has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: ULTIMATE.startFINAL has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L9-2 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L26-1 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L13 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L13 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L12-2 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: assume_abort_if_notEXIT has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L46-2 has no Hoare annotation [2022-04-14 17:24:36,462 WARN L170 areAnnotationChecker]: L46-2 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L33-3 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L33-3 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L33-1 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L33-1 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L34-1 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L34-1 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L56 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L56 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L57 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L34 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L34 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L39 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L39 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: mainFINAL has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L43 has no Hoare annotation [2022-04-14 17:24:36,463 WARN L170 areAnnotationChecker]: L43 has no Hoare annotation [2022-04-14 17:24:36,464 WARN L170 areAnnotationChecker]: mainEXIT has no Hoare annotation [2022-04-14 17:24:36,464 WARN L170 areAnnotationChecker]: L46 has no Hoare annotation [2022-04-14 17:24:36,464 WARN L170 areAnnotationChecker]: L46 has no Hoare annotation [2022-04-14 17:24:36,464 INFO L163 areAnnotationChecker]: CFG has 0 edges. 0 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. 0 times interpolants missing. [2022-04-14 17:24:36,464 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 14.04 05:24:36 BoogieIcfgContainer [2022-04-14 17:24:36,464 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-14 17:24:36,465 INFO L158 Benchmark]: Toolchain (without parser) took 147066.15ms. Allocated memory was 176.2MB in the beginning and 219.2MB in the end (delta: 43.0MB). Free memory was 126.2MB in the beginning and 104.1MB in the end (delta: 22.1MB). Peak memory consumption was 65.3MB. Max. memory is 8.0GB. [2022-04-14 17:24:36,465 INFO L158 Benchmark]: CDTParser took 0.13ms. Allocated memory is still 176.2MB. Free memory is still 142.6MB. There was no memory consumed. Max. memory is 8.0GB. [2022-04-14 17:24:36,466 INFO L158 Benchmark]: CACSL2BoogieTranslator took 224.49ms. Allocated memory is still 176.2MB. Free memory was 126.0MB in the beginning and 154.9MB in the end (delta: -28.9MB). Peak memory consumption was 14.9MB. Max. memory is 8.0GB. [2022-04-14 17:24:36,466 INFO L158 Benchmark]: Boogie Preprocessor took 39.22ms. Allocated memory is still 176.2MB. Free memory was 154.9MB in the beginning and 153.4MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-14 17:24:36,466 INFO L158 Benchmark]: RCFGBuilder took 270.26ms. Allocated memory is still 176.2MB. Free memory was 153.4MB in the beginning and 140.3MB in the end (delta: 13.1MB). Peak memory consumption was 13.6MB. Max. memory is 8.0GB. [2022-04-14 17:24:36,466 INFO L158 Benchmark]: TraceAbstraction took 146524.67ms. Allocated memory was 176.2MB in the beginning and 219.2MB in the end (delta: 43.0MB). Free memory was 139.8MB in the beginning and 104.1MB in the end (delta: 35.7MB). Peak memory consumption was 79.7MB. Max. memory is 8.0GB. [2022-04-14 17:24:36,468 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - AssertionsEnabledResult: Assertions are enabled Assertions are enabled - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.13ms. Allocated memory is still 176.2MB. Free memory is still 142.6MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 224.49ms. Allocated memory is still 176.2MB. Free memory was 126.0MB in the beginning and 154.9MB in the end (delta: -28.9MB). Peak memory consumption was 14.9MB. Max. memory is 8.0GB. * Boogie Preprocessor took 39.22ms. Allocated memory is still 176.2MB. Free memory was 154.9MB in the beginning and 153.4MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 270.26ms. Allocated memory is still 176.2MB. Free memory was 153.4MB in the beginning and 140.3MB in the end (delta: 13.1MB). Peak memory consumption was 13.6MB. Max. memory is 8.0GB. * TraceAbstraction took 146524.67ms. Allocated memory was 176.2MB in the beginning and 219.2MB in the end (delta: 43.0MB). Free memory was 139.8MB in the beginning and 104.1MB in the end (delta: 35.7MB). Peak memory consumption was 79.7MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 14]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L19] int counter = 0; VAL [\old(counter)=7, counter=0] [L21] int x, y; [L22] long long a, b, p, q; [L24] x = __VERIFIER_nondet_int() [L25] y = __VERIFIER_nondet_int() [L26] CALL assume_abort_if_not(y >= 1) VAL [\old(cond)=1, \old(counter)=0, counter=0] [L9] COND FALSE !(!cond) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=0] [L26] RET assume_abort_if_not(y >= 1) VAL [\old(counter)=0, counter=0, x=4, y=4] [L28] a = x [L29] b = y [L30] p = 1 [L31] q = 0 VAL [\old(counter)=0, a=4, b=4, counter=0, p=1, q=0, x=4, y=4] [L33] EXPR counter++ VAL [\old(counter)=0, a=4, b=4, counter=1, counter++=0, p=1, q=0, x=4, y=4] [L33] COND TRUE counter++<2 [L34] CALL __VERIFIER_assert(q + a * b * p == (long long) x * y) VAL [\old(cond)=1, \old(counter)=0, counter=1] [L12] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=1] [L34] RET __VERIFIER_assert(q + a * b * p == (long long) x * y) VAL [\old(counter)=0, a=4, b=4, counter=1, p=1, q=0, x=4, y=4] [L36] COND FALSE !(!(a != 0 && b != 0)) VAL [\old(counter)=0, a=4, b=4, counter=1, p=1, q=0, x=4, y=4] [L39] COND TRUE a % 2 == 0 && b % 2 == 0 [L40] a = a / 2 [L41] b = b / 2 [L42] p = 4 * p VAL [\old(counter)=0, a=2, b=2, counter=1, p=4, q=0, x=4, y=4] [L33] EXPR counter++ VAL [\old(counter)=0, a=2, b=2, counter=2, counter++=1, p=4, q=0, x=4, y=4] [L33] COND TRUE counter++<2 [L34] CALL __VERIFIER_assert(q + a * b * p == (long long) x * y) VAL [\old(cond)=1, \old(counter)=0, counter=2] [L12] COND FALSE !(!(cond)) VAL [\old(cond)=1, \old(counter)=0, cond=1, counter=2] [L34] RET __VERIFIER_assert(q + a * b * p == (long long) x * y) VAL [\old(counter)=0, a=2, b=2, counter=2, p=4, q=0, x=4, y=4] [L36] COND FALSE !(!(a != 0 && b != 0)) VAL [\old(counter)=0, a=2, b=2, counter=2, p=4, q=0, x=4, y=4] [L39] COND TRUE a % 2 == 0 && b % 2 == 0 [L40] a = a / 2 [L41] b = b / 2 [L42] p = 4 * p VAL [\old(counter)=0, a=1, b=1, counter=2, p=16, q=0, x=4, y=4] [L33] EXPR counter++ VAL [\old(counter)=0, a=1, b=1, counter=3, counter++=2, p=16, q=0, x=4, y=4] [L33] COND FALSE !(counter++<2) [L56] CALL __VERIFIER_assert(q == (long long) x * y) VAL [\old(cond)=0, \old(counter)=0, counter=3] [L12] COND TRUE !(cond) VAL [\old(cond)=0, \old(counter)=0, cond=0, counter=3] [L14] reach_error() VAL [\old(cond)=0, \old(counter)=0, cond=0, counter=3] - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 35 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 146.4s, OverallIterations: 8, TraceHistogramMax: 3, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 9.5s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 217 SdHoareTripleChecker+Valid, 3.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 205 mSDsluCounter, 755 SdHoareTripleChecker+Invalid, 3.0s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 560 mSDsCounter, 133 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 787 IncrementalHoareTripleChecker+Invalid, 920 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 133 mSolverCounterUnsat, 195 mSDtfsCounter, 787 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 239 GetRequests, 176 SyntacticMatches, 3 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 1.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=57occurred in iteration=6, InterpolantAutomatonStates: 54, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 7 MinimizatonAttempts, 43 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 132.2s InterpolantComputationTime, 196 NumberOfCodeBlocks, 196 NumberOfCodeBlocksAsserted, 9 NumberOfCheckSat, 228 ConstructedInterpolants, 0 QuantifiedInterpolants, 1056 SizeOfPredicates, 20 NumberOfNonLiveVariables, 597 ConjunctsInSsa, 86 ConjunctsInUnsatCore, 10 InterpolantComputations, 4 PerfectInterpolantSequences, 16/30 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 RESULT: Ultimate proved your program to be incorrect! [2022-04-14 17:24:36,514 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...