/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/cohendiv-ll_valuebound1.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-07 13:01:30,925 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-07 13:01:30,926 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-07 13:01:30,977 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-07 13:01:30,978 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-07 13:01:30,978 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-07 13:01:30,981 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-07 13:01:30,984 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-07 13:01:30,985 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-07 13:01:30,989 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-07 13:01:30,989 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-07 13:01:30,990 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-07 13:01:30,990 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-07 13:01:30,992 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-07 13:01:30,993 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-07 13:01:30,995 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-07 13:01:30,995 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-07 13:01:30,996 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-07 13:01:30,997 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-07 13:01:31,001 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-07 13:01:31,002 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-07 13:01:31,003 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-07 13:01:31,004 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-07 13:01:31,004 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-07 13:01:31,005 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-07 13:01:31,010 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-07 13:01:31,010 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-07 13:01:31,010 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-07 13:01:31,010 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-07 13:01:31,011 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-07 13:01:31,012 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-07 13:01:31,012 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-07 13:01:31,013 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-07 13:01:31,013 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-07 13:01:31,014 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-07 13:01:31,014 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-07 13:01:31,015 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-07 13:01:31,015 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-07 13:01:31,015 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-07 13:01:31,015 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-07 13:01:31,016 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-07 13:01:31,017 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-07 13:01:31,017 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-07 13:01:31,047 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-07 13:01:31,047 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-07 13:01:31,047 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-04-07 13:01:31,047 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-04-07 13:01:31,048 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-07 13:01:31,048 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-07 13:01:31,048 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-07 13:01:31,049 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-07 13:01:31,049 INFO L138 SettingsManager]: * Use SBE=true [2022-04-07 13:01:31,049 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-07 13:01:31,049 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-07 13:01:31,049 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-07 13:01:31,050 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-07 13:01:31,050 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-07 13:01:31,050 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-07 13:01:31,050 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-07 13:01:31,050 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-07 13:01:31,051 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-07 13:01:31,051 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-07 13:01:31,051 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-07 13:01:31,051 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-07 13:01:31,051 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-07 13:01:31,051 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-07 13:01:31,051 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-07 13:01:31,052 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-07 13:01:31,052 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-07 13:01:31,052 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-07 13:01:31,052 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-07 13:01:31,052 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-07 13:01:31,052 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-07 13:01:31,052 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2022-04-07 13:01:31,052 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-04-07 13:01:31,053 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-07 13:01:31,053 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-07 13:01:31,233 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-07 13:01:31,254 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-07 13:01:31,255 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-07 13:01:31,256 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-07 13:01:31,257 INFO L275 PluginConnector]: CDTParser initialized [2022-04-07 13:01:31,258 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/cohendiv-ll_valuebound1.c [2022-04-07 13:01:31,298 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8e816bca4/e1a0b6322eb445fab534e39379a03636/FLAG34c13bed7 [2022-04-07 13:01:31,664 INFO L306 CDTParser]: Found 1 translation units. [2022-04-07 13:01:31,664 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohendiv-ll_valuebound1.c [2022-04-07 13:01:31,670 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8e816bca4/e1a0b6322eb445fab534e39379a03636/FLAG34c13bed7 [2022-04-07 13:01:31,680 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8e816bca4/e1a0b6322eb445fab534e39379a03636 [2022-04-07 13:01:31,682 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-07 13:01:31,683 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-07 13:01:31,685 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-07 13:01:31,685 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-07 13:01:31,687 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-07 13:01:31,688 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.04 01:01:31" (1/1) ... [2022-04-07 13:01:31,689 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7954c047 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 01:01:31, skipping insertion in model container [2022-04-07 13:01:31,689 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 07.04 01:01:31" (1/1) ... [2022-04-07 13:01:31,693 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-07 13:01:31,704 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-07 13:01:31,831 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/cohendiv-ll_valuebound1.c[576,589] [2022-04-07 13:01:31,842 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-07 13:01:31,848 INFO L203 MainTranslator]: Completed pre-run [2022-04-07 13:01:31,855 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/cohendiv-ll_valuebound1.c[576,589] [2022-04-07 13:01:31,860 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-07 13:01:31,869 INFO L208 MainTranslator]: Completed translation [2022-04-07 13:01:31,869 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 01:01:31 WrapperNode [2022-04-07 13:01:31,869 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-07 13:01:31,870 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-07 13:01:31,870 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-07 13:01:31,870 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-07 13:01:31,876 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 01:01:31" (1/1) ... [2022-04-07 13:01:31,876 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 01:01:31" (1/1) ... [2022-04-07 13:01:31,880 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 01:01:31" (1/1) ... [2022-04-07 13:01:31,880 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 01:01:31" (1/1) ... [2022-04-07 13:01:31,884 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 01:01:31" (1/1) ... [2022-04-07 13:01:31,887 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 01:01:31" (1/1) ... [2022-04-07 13:01:31,892 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 01:01:31" (1/1) ... [2022-04-07 13:01:31,894 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-07 13:01:31,894 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-07 13:01:31,894 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-07 13:01:31,894 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-07 13:01:31,895 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 01:01:31" (1/1) ... [2022-04-07 13:01:31,902 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-07 13:01:31,909 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 13:01:31,920 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-07 13:01:31,931 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-07 13:01:31,944 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-07 13:01:31,945 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-07 13:01:31,945 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-07 13:01:31,945 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-07 13:01:31,945 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-07 13:01:31,945 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-07 13:01:31,945 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-07 13:01:31,945 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-07 13:01:31,945 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-07 13:01:31,945 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-07 13:01:31,945 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-07 13:01:31,945 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-07 13:01:31,945 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-07 13:01:31,945 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-07 13:01:31,945 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-07 13:01:31,945 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-07 13:01:31,946 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-07 13:01:31,946 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-07 13:01:31,946 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-07 13:01:31,946 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-07 13:01:31,988 INFO L234 CfgBuilder]: Building ICFG [2022-04-07 13:01:31,989 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-07 13:01:32,158 INFO L275 CfgBuilder]: Performing block encoding [2022-04-07 13:01:32,162 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-07 13:01:32,163 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-07 13:01:32,164 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.04 01:01:32 BoogieIcfgContainer [2022-04-07 13:01:32,164 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-07 13:01:32,165 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-07 13:01:32,165 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-07 13:01:32,167 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-07 13:01:32,167 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 07.04 01:01:31" (1/3) ... [2022-04-07 13:01:32,167 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@291b05c1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.04 01:01:32, skipping insertion in model container [2022-04-07 13:01:32,168 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 07.04 01:01:31" (2/3) ... [2022-04-07 13:01:32,168 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@291b05c1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 07.04 01:01:32, skipping insertion in model container [2022-04-07 13:01:32,168 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 07.04 01:01:32" (3/3) ... [2022-04-07 13:01:32,169 INFO L111 eAbstractionObserver]: Analyzing ICFG cohendiv-ll_valuebound1.c [2022-04-07 13:01:32,180 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-07 13:01:32,180 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-07 13:01:32,225 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-07 13:01:32,233 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-07 13:01:32,233 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-07 13:01:32,248 INFO L276 IsEmpty]: Start isEmpty. Operand has 39 states, 21 states have (on average 1.4285714285714286) internal successors, (30), 22 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-07 13:01:32,253 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-07 13:01:32,254 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 13:01:32,254 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 13:01:32,255 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 13:01:32,258 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 13:01:32,259 INFO L85 PathProgramCache]: Analyzing trace with hash -1768835633, now seen corresponding path program 1 times [2022-04-07 13:01:32,266 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 13:01:32,267 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1732518498] [2022-04-07 13:01:32,267 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 13:01:32,267 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 13:01:32,375 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:32,426 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-07 13:01:32,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:32,453 INFO L290 TraceCheckUtils]: 0: Hoare triple {59#(and (= |#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(14, 2);call #Ultimate.allocInit(12, 3); {42#true} is VALID [2022-04-07 13:01:32,453 INFO L290 TraceCheckUtils]: 1: Hoare triple {42#true} assume true; {42#true} is VALID [2022-04-07 13:01:32,453 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {42#true} {42#true} #98#return; {42#true} is VALID [2022-04-07 13:01:32,454 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-07 13:01:32,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:32,474 INFO L290 TraceCheckUtils]: 0: Hoare triple {42#true} ~cond := #in~cond; {42#true} is VALID [2022-04-07 13:01:32,474 INFO L290 TraceCheckUtils]: 1: Hoare triple {42#true} assume 0 == ~cond;assume false; {43#false} is VALID [2022-04-07 13:01:32,474 INFO L290 TraceCheckUtils]: 2: Hoare triple {43#false} assume true; {43#false} is VALID [2022-04-07 13:01:32,475 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {43#false} {42#true} #78#return; {43#false} is VALID [2022-04-07 13:01:32,475 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-07 13:01:32,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:32,483 INFO L290 TraceCheckUtils]: 0: Hoare triple {42#true} ~cond := #in~cond; {42#true} is VALID [2022-04-07 13:01:32,483 INFO L290 TraceCheckUtils]: 1: Hoare triple {42#true} assume 0 == ~cond;assume false; {43#false} is VALID [2022-04-07 13:01:32,484 INFO L290 TraceCheckUtils]: 2: Hoare triple {43#false} assume true; {43#false} is VALID [2022-04-07 13:01:32,484 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {43#false} {43#false} #80#return; {43#false} is VALID [2022-04-07 13:01:32,484 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-07 13:01:32,487 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:32,495 INFO L290 TraceCheckUtils]: 0: Hoare triple {42#true} ~cond := #in~cond; {42#true} is VALID [2022-04-07 13:01:32,495 INFO L290 TraceCheckUtils]: 1: Hoare triple {42#true} assume 0 == ~cond;assume false; {43#false} is VALID [2022-04-07 13:01:32,495 INFO L290 TraceCheckUtils]: 2: Hoare triple {43#false} assume true; {43#false} is VALID [2022-04-07 13:01:32,496 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {43#false} {43#false} #82#return; {43#false} is VALID [2022-04-07 13:01:32,496 INFO L272 TraceCheckUtils]: 0: Hoare triple {42#true} call ULTIMATE.init(); {59#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-07 13:01:32,497 INFO L290 TraceCheckUtils]: 1: Hoare triple {59#(and (= |#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(14, 2);call #Ultimate.allocInit(12, 3); {42#true} is VALID [2022-04-07 13:01:32,497 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#true} assume true; {42#true} is VALID [2022-04-07 13:01:32,497 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#true} {42#true} #98#return; {42#true} is VALID [2022-04-07 13:01:32,497 INFO L272 TraceCheckUtils]: 4: Hoare triple {42#true} call #t~ret6 := main(); {42#true} is VALID [2022-04-07 13:01:32,498 INFO L290 TraceCheckUtils]: 5: Hoare triple {42#true} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4; {42#true} is VALID [2022-04-07 13:01:32,498 INFO L272 TraceCheckUtils]: 6: Hoare triple {42#true} call assume_abort_if_not((if ~x~0 >= 0 && ~x~0 <= 1 then 1 else 0)); {42#true} is VALID [2022-04-07 13:01:32,498 INFO L290 TraceCheckUtils]: 7: Hoare triple {42#true} ~cond := #in~cond; {42#true} is VALID [2022-04-07 13:01:32,499 INFO L290 TraceCheckUtils]: 8: Hoare triple {42#true} assume 0 == ~cond;assume false; {43#false} is VALID [2022-04-07 13:01:32,499 INFO L290 TraceCheckUtils]: 9: Hoare triple {43#false} assume true; {43#false} is VALID [2022-04-07 13:01:32,500 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {43#false} {42#true} #78#return; {43#false} is VALID [2022-04-07 13:01:32,500 INFO L290 TraceCheckUtils]: 11: Hoare triple {43#false} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {43#false} is VALID [2022-04-07 13:01:32,501 INFO L272 TraceCheckUtils]: 12: Hoare triple {43#false} call assume_abort_if_not((if ~y~0 >= 0 && ~y~0 <= 1 then 1 else 0)); {42#true} is VALID [2022-04-07 13:01:32,501 INFO L290 TraceCheckUtils]: 13: Hoare triple {42#true} ~cond := #in~cond; {42#true} is VALID [2022-04-07 13:01:32,501 INFO L290 TraceCheckUtils]: 14: Hoare triple {42#true} assume 0 == ~cond;assume false; {43#false} is VALID [2022-04-07 13:01:32,502 INFO L290 TraceCheckUtils]: 15: Hoare triple {43#false} assume true; {43#false} is VALID [2022-04-07 13:01:32,502 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {43#false} {43#false} #80#return; {43#false} is VALID [2022-04-07 13:01:32,502 INFO L272 TraceCheckUtils]: 17: Hoare triple {43#false} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {42#true} is VALID [2022-04-07 13:01:32,502 INFO L290 TraceCheckUtils]: 18: Hoare triple {42#true} ~cond := #in~cond; {42#true} is VALID [2022-04-07 13:01:32,503 INFO L290 TraceCheckUtils]: 19: Hoare triple {42#true} assume 0 == ~cond;assume false; {43#false} is VALID [2022-04-07 13:01:32,503 INFO L290 TraceCheckUtils]: 20: Hoare triple {43#false} assume true; {43#false} is VALID [2022-04-07 13:01:32,503 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {43#false} {43#false} #82#return; {43#false} is VALID [2022-04-07 13:01:32,504 INFO L290 TraceCheckUtils]: 22: Hoare triple {43#false} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {43#false} is VALID [2022-04-07 13:01:32,504 INFO L290 TraceCheckUtils]: 23: Hoare triple {43#false} assume false; {43#false} is VALID [2022-04-07 13:01:32,505 INFO L272 TraceCheckUtils]: 24: Hoare triple {43#false} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {43#false} is VALID [2022-04-07 13:01:32,505 INFO L290 TraceCheckUtils]: 25: Hoare triple {43#false} ~cond := #in~cond; {43#false} is VALID [2022-04-07 13:01:32,505 INFO L290 TraceCheckUtils]: 26: Hoare triple {43#false} assume 0 == ~cond; {43#false} is VALID [2022-04-07 13:01:32,505 INFO L290 TraceCheckUtils]: 27: Hoare triple {43#false} assume !false; {43#false} is VALID [2022-04-07 13:01:32,505 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-07 13:01:32,506 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 13:01:32,506 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1732518498] [2022-04-07 13:01:32,506 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1732518498] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 13:01:32,506 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 13:01:32,507 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-07 13:01:32,509 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [217979014] [2022-04-07 13:01:32,510 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 13:01:32,514 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-07 13:01:32,516 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-07 13:01:32,518 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-07 13:01:32,548 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 22 edges. 22 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 13:01:32,549 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-07 13:01:32,549 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-07 13:01:32,573 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-07 13:01:32,573 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-07 13:01:32,576 INFO L87 Difference]: Start difference. First operand has 39 states, 21 states have (on average 1.4285714285714286) internal successors, (30), 22 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-07 13:01:32,727 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:32,727 INFO L93 Difference]: Finished difference Result 71 states and 110 transitions. [2022-04-07 13:01:32,727 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-07 13:01:32,728 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-07 13:01:32,728 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 13:01:32,729 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-07 13:01:32,737 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 110 transitions. [2022-04-07 13:01:32,737 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-07 13:01:32,742 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 110 transitions. [2022-04-07 13:01:32,742 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 110 transitions. [2022-04-07 13:01:32,859 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 110 edges. 110 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 13:01:32,866 INFO L225 Difference]: With dead ends: 71 [2022-04-07 13:01:32,866 INFO L226 Difference]: Without dead ends: 34 [2022-04-07 13:01:32,868 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 12 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-07 13:01:32,870 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 21 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-07 13:01:32,871 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 41 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-07 13:01:32,881 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2022-04-07 13:01:32,894 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2022-04-07 13:01:32,894 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-07 13:01:32,895 INFO L82 GeneralOperation]: Start isEquivalent. First operand 34 states. Second operand has 34 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-07 13:01:32,896 INFO L74 IsIncluded]: Start isIncluded. First operand 34 states. Second operand has 34 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-07 13:01:32,896 INFO L87 Difference]: Start difference. First operand 34 states. Second operand has 34 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-07 13:01:32,900 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:32,900 INFO L93 Difference]: Finished difference Result 34 states and 43 transitions. [2022-04-07 13:01:32,900 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 43 transitions. [2022-04-07 13:01:32,901 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:32,901 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:32,902 INFO L74 IsIncluded]: Start isIncluded. First operand has 34 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 34 states. [2022-04-07 13:01:32,902 INFO L87 Difference]: Start difference. First operand has 34 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand 34 states. [2022-04-07 13:01:32,907 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:32,907 INFO L93 Difference]: Finished difference Result 34 states and 43 transitions. [2022-04-07 13:01:32,907 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 43 transitions. [2022-04-07 13:01:32,907 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:32,907 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:32,908 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-07 13:01:32,908 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-07 13:01:32,908 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-07 13:01:32,910 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 43 transitions. [2022-04-07 13:01:32,911 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 43 transitions. Word has length 28 [2022-04-07 13:01:32,911 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 13:01:32,929 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 43 transitions. [2022-04-07 13:01:32,929 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-07 13:01:32,930 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 43 transitions. [2022-04-07 13:01:32,930 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-07 13:01:32,930 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 13:01:32,930 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 13:01:32,930 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-07 13:01:32,931 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 13:01:32,931 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 13:01:32,931 INFO L85 PathProgramCache]: Analyzing trace with hash 1378913883, now seen corresponding path program 1 times [2022-04-07 13:01:32,931 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 13:01:32,932 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1323164752] [2022-04-07 13:01:32,932 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 13:01:32,932 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 13:01:32,964 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 13:01:32,965 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1536319711] [2022-04-07 13:01:32,965 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 13:01:32,965 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 13:01:32,965 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 13:01:32,972 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-07 13:01:32,972 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-07 13:01:33,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:33,021 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-07 13:01:33,030 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:33,034 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 13:01:33,343 INFO L272 TraceCheckUtils]: 0: Hoare triple {284#true} call ULTIMATE.init(); {284#true} is VALID [2022-04-07 13:01:33,343 INFO L290 TraceCheckUtils]: 1: Hoare triple {284#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(14, 2);call #Ultimate.allocInit(12, 3); {284#true} is VALID [2022-04-07 13:01:33,343 INFO L290 TraceCheckUtils]: 2: Hoare triple {284#true} assume true; {284#true} is VALID [2022-04-07 13:01:33,343 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {284#true} {284#true} #98#return; {284#true} is VALID [2022-04-07 13:01:33,344 INFO L272 TraceCheckUtils]: 4: Hoare triple {284#true} call #t~ret6 := main(); {284#true} is VALID [2022-04-07 13:01:33,346 INFO L290 TraceCheckUtils]: 5: Hoare triple {284#true} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4; {284#true} is VALID [2022-04-07 13:01:33,346 INFO L272 TraceCheckUtils]: 6: Hoare triple {284#true} call assume_abort_if_not((if ~x~0 >= 0 && ~x~0 <= 1 then 1 else 0)); {284#true} is VALID [2022-04-07 13:01:33,346 INFO L290 TraceCheckUtils]: 7: Hoare triple {284#true} ~cond := #in~cond; {284#true} is VALID [2022-04-07 13:01:33,346 INFO L290 TraceCheckUtils]: 8: Hoare triple {284#true} assume !(0 == ~cond); {284#true} is VALID [2022-04-07 13:01:33,346 INFO L290 TraceCheckUtils]: 9: Hoare triple {284#true} assume true; {284#true} is VALID [2022-04-07 13:01:33,352 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {284#true} {284#true} #78#return; {284#true} is VALID [2022-04-07 13:01:33,352 INFO L290 TraceCheckUtils]: 11: Hoare triple {284#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {284#true} is VALID [2022-04-07 13:01:33,353 INFO L272 TraceCheckUtils]: 12: Hoare triple {284#true} call assume_abort_if_not((if ~y~0 >= 0 && ~y~0 <= 1 then 1 else 0)); {284#true} is VALID [2022-04-07 13:01:33,354 INFO L290 TraceCheckUtils]: 13: Hoare triple {284#true} ~cond := #in~cond; {328#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-07 13:01:33,354 INFO L290 TraceCheckUtils]: 14: Hoare triple {328#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {332#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:33,355 INFO L290 TraceCheckUtils]: 15: Hoare triple {332#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {332#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:33,355 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {332#(not (= |assume_abort_if_not_#in~cond| 0))} {284#true} #80#return; {339#(and (<= 0 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:33,355 INFO L272 TraceCheckUtils]: 17: Hoare triple {339#(and (<= 0 main_~y~0) (<= main_~y~0 1))} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {284#true} is VALID [2022-04-07 13:01:33,356 INFO L290 TraceCheckUtils]: 18: Hoare triple {284#true} ~cond := #in~cond; {328#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-07 13:01:33,356 INFO L290 TraceCheckUtils]: 19: Hoare triple {328#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {332#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:33,356 INFO L290 TraceCheckUtils]: 20: Hoare triple {332#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {332#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:33,357 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {332#(not (= |assume_abort_if_not_#in~cond| 0))} {339#(and (<= 0 main_~y~0) (<= main_~y~0 1))} #82#return; {355#(and (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:33,357 INFO L290 TraceCheckUtils]: 22: Hoare triple {355#(and (<= 1 main_~y~0) (<= main_~y~0 1))} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {359#(and (= main_~a~0 0) (= main_~b~0 0) (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:33,358 INFO L290 TraceCheckUtils]: 23: Hoare triple {359#(and (= main_~a~0 0) (= main_~b~0 0) (<= 1 main_~y~0) (<= main_~y~0 1))} assume !false; {359#(and (= main_~a~0 0) (= main_~b~0 0) (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:33,359 INFO L272 TraceCheckUtils]: 24: Hoare triple {359#(and (= main_~a~0 0) (= main_~b~0 0) (<= 1 main_~y~0) (<= main_~y~0 1))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {366#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-07 13:01:33,359 INFO L290 TraceCheckUtils]: 25: Hoare triple {366#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {370#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-07 13:01:33,360 INFO L290 TraceCheckUtils]: 26: Hoare triple {370#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {285#false} is VALID [2022-04-07 13:01:33,360 INFO L290 TraceCheckUtils]: 27: Hoare triple {285#false} assume !false; {285#false} is VALID [2022-04-07 13:01:33,361 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-04-07 13:01:33,361 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-07 13:01:33,361 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 13:01:33,361 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1323164752] [2022-04-07 13:01:33,361 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 13:01:33,361 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1536319711] [2022-04-07 13:01:33,364 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1536319711] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 13:01:33,364 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 13:01:33,364 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-07 13:01:33,365 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1934568636] [2022-04-07 13:01:33,365 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 13:01:33,366 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-07 13:01:33,367 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-07 13:01:33,367 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-07 13:01:33,383 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 25 edges. 25 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 13:01:33,383 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-07 13:01:33,384 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-07 13:01:33,385 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-07 13:01:33,385 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2022-04-07 13:01:33,385 INFO L87 Difference]: Start difference. First operand 34 states and 43 transitions. Second operand has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-07 13:01:33,742 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:33,742 INFO L93 Difference]: Finished difference Result 45 states and 56 transitions. [2022-04-07 13:01:33,742 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-07 13:01:33,743 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-07 13:01:33,743 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 13:01:33,743 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-07 13:01:33,745 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 56 transitions. [2022-04-07 13:01:33,745 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-07 13:01:33,747 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 56 transitions. [2022-04-07 13:01:33,747 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 9 states and 56 transitions. [2022-04-07 13:01:33,787 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 56 edges. 56 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 13:01:33,789 INFO L225 Difference]: With dead ends: 45 [2022-04-07 13:01:33,789 INFO L226 Difference]: Without dead ends: 43 [2022-04-07 13:01:33,789 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-04-07 13:01:33,790 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 28 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 120 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 128 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 120 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-07 13:01:33,790 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [37 Valid, 169 Invalid, 128 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 120 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-07 13:01:33,791 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2022-04-07 13:01:33,806 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 40. [2022-04-07 13:01:33,806 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-07 13:01:33,807 INFO L82 GeneralOperation]: Start isEquivalent. First operand 43 states. Second operand has 40 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 24 states have internal predecessors, (25), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-07 13:01:33,809 INFO L74 IsIncluded]: Start isIncluded. First operand 43 states. Second operand has 40 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 24 states have internal predecessors, (25), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-07 13:01:33,809 INFO L87 Difference]: Start difference. First operand 43 states. Second operand has 40 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 24 states have internal predecessors, (25), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-07 13:01:33,817 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:33,817 INFO L93 Difference]: Finished difference Result 43 states and 54 transitions. [2022-04-07 13:01:33,819 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 54 transitions. [2022-04-07 13:01:33,823 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:33,824 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:33,824 INFO L74 IsIncluded]: Start isIncluded. First operand has 40 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 24 states have internal predecessors, (25), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) Second operand 43 states. [2022-04-07 13:01:33,824 INFO L87 Difference]: Start difference. First operand has 40 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 24 states have internal predecessors, (25), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) Second operand 43 states. [2022-04-07 13:01:33,826 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:33,826 INFO L93 Difference]: Finished difference Result 43 states and 54 transitions. [2022-04-07 13:01:33,826 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 54 transitions. [2022-04-07 13:01:33,826 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:33,827 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:33,827 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-07 13:01:33,827 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-07 13:01:33,827 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 24 states have internal predecessors, (25), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-07 13:01:33,828 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 49 transitions. [2022-04-07 13:01:33,829 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 49 transitions. Word has length 28 [2022-04-07 13:01:33,829 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 13:01:33,829 INFO L478 AbstractCegarLoop]: Abstraction has 40 states and 49 transitions. [2022-04-07 13:01:33,829 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-07 13:01:33,829 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 49 transitions. [2022-04-07 13:01:33,829 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-04-07 13:01:33,830 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 13:01:33,830 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 13:01:33,853 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-07 13:01:34,043 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-07 13:01:34,044 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 13:01:34,044 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 13:01:34,044 INFO L85 PathProgramCache]: Analyzing trace with hash -1928335320, now seen corresponding path program 1 times [2022-04-07 13:01:34,044 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 13:01:34,044 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [326100732] [2022-04-07 13:01:34,044 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 13:01:34,044 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 13:01:34,059 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 13:01:34,059 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1169274952] [2022-04-07 13:01:34,059 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 13:01:34,060 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 13:01:34,060 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 13:01:34,063 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-07 13:01:34,065 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-07 13:01:34,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:34,116 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-07 13:01:34,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:34,128 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 13:01:34,320 INFO L272 TraceCheckUtils]: 0: Hoare triple {595#true} call ULTIMATE.init(); {595#true} is VALID [2022-04-07 13:01:34,320 INFO L290 TraceCheckUtils]: 1: Hoare triple {595#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(14, 2);call #Ultimate.allocInit(12, 3); {595#true} is VALID [2022-04-07 13:01:34,321 INFO L290 TraceCheckUtils]: 2: Hoare triple {595#true} assume true; {595#true} is VALID [2022-04-07 13:01:34,321 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {595#true} {595#true} #98#return; {595#true} is VALID [2022-04-07 13:01:34,321 INFO L272 TraceCheckUtils]: 4: Hoare triple {595#true} call #t~ret6 := main(); {595#true} is VALID [2022-04-07 13:01:34,321 INFO L290 TraceCheckUtils]: 5: Hoare triple {595#true} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4; {595#true} is VALID [2022-04-07 13:01:34,321 INFO L272 TraceCheckUtils]: 6: Hoare triple {595#true} call assume_abort_if_not((if ~x~0 >= 0 && ~x~0 <= 1 then 1 else 0)); {595#true} is VALID [2022-04-07 13:01:34,321 INFO L290 TraceCheckUtils]: 7: Hoare triple {595#true} ~cond := #in~cond; {595#true} is VALID [2022-04-07 13:01:34,321 INFO L290 TraceCheckUtils]: 8: Hoare triple {595#true} assume !(0 == ~cond); {595#true} is VALID [2022-04-07 13:01:34,321 INFO L290 TraceCheckUtils]: 9: Hoare triple {595#true} assume true; {595#true} is VALID [2022-04-07 13:01:34,321 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {595#true} {595#true} #78#return; {595#true} is VALID [2022-04-07 13:01:34,322 INFO L290 TraceCheckUtils]: 11: Hoare triple {595#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {595#true} is VALID [2022-04-07 13:01:34,322 INFO L272 TraceCheckUtils]: 12: Hoare triple {595#true} call assume_abort_if_not((if ~y~0 >= 0 && ~y~0 <= 1 then 1 else 0)); {595#true} is VALID [2022-04-07 13:01:34,322 INFO L290 TraceCheckUtils]: 13: Hoare triple {595#true} ~cond := #in~cond; {639#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-07 13:01:34,323 INFO L290 TraceCheckUtils]: 14: Hoare triple {639#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {643#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:34,323 INFO L290 TraceCheckUtils]: 15: Hoare triple {643#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {643#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:34,324 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {643#(not (= |assume_abort_if_not_#in~cond| 0))} {595#true} #80#return; {650#(and (<= 0 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:34,324 INFO L272 TraceCheckUtils]: 17: Hoare triple {650#(and (<= 0 main_~y~0) (<= main_~y~0 1))} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {595#true} is VALID [2022-04-07 13:01:34,324 INFO L290 TraceCheckUtils]: 18: Hoare triple {595#true} ~cond := #in~cond; {639#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-07 13:01:34,324 INFO L290 TraceCheckUtils]: 19: Hoare triple {639#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {643#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:34,325 INFO L290 TraceCheckUtils]: 20: Hoare triple {643#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {643#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:34,325 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {643#(not (= |assume_abort_if_not_#in~cond| 0))} {650#(and (<= 0 main_~y~0) (<= main_~y~0 1))} #82#return; {666#(and (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:34,326 INFO L290 TraceCheckUtils]: 22: Hoare triple {666#(and (<= 1 main_~y~0) (<= main_~y~0 1))} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {670#(and (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:34,326 INFO L290 TraceCheckUtils]: 23: Hoare triple {670#(and (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= 1 main_~y~0) (<= main_~y~0 1))} assume !false; {670#(and (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:34,326 INFO L272 TraceCheckUtils]: 24: Hoare triple {670#(and (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= 1 main_~y~0) (<= main_~y~0 1))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {595#true} is VALID [2022-04-07 13:01:34,326 INFO L290 TraceCheckUtils]: 25: Hoare triple {595#true} ~cond := #in~cond; {595#true} is VALID [2022-04-07 13:01:34,326 INFO L290 TraceCheckUtils]: 26: Hoare triple {595#true} assume !(0 == ~cond); {595#true} is VALID [2022-04-07 13:01:34,326 INFO L290 TraceCheckUtils]: 27: Hoare triple {595#true} assume true; {595#true} is VALID [2022-04-07 13:01:34,327 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {595#true} {670#(and (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= 1 main_~y~0) (<= main_~y~0 1))} #84#return; {670#(and (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:34,328 INFO L272 TraceCheckUtils]: 29: Hoare triple {670#(and (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= 1 main_~y~0) (<= main_~y~0 1))} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {692#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-07 13:01:34,328 INFO L290 TraceCheckUtils]: 30: Hoare triple {692#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {696#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-07 13:01:34,330 INFO L290 TraceCheckUtils]: 31: Hoare triple {696#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {596#false} is VALID [2022-04-07 13:01:34,330 INFO L290 TraceCheckUtils]: 32: Hoare triple {596#false} assume !false; {596#false} is VALID [2022-04-07 13:01:34,330 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-04-07 13:01:34,330 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-07 13:01:34,330 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 13:01:34,330 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [326100732] [2022-04-07 13:01:34,330 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 13:01:34,330 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1169274952] [2022-04-07 13:01:34,330 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1169274952] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 13:01:34,331 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 13:01:34,331 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-07 13:01:34,331 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [805804034] [2022-04-07 13:01:34,331 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 13:01:34,331 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) Word has length 33 [2022-04-07 13:01:34,331 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-07 13:01:34,332 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 9 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-07 13:01:34,354 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 30 edges. 30 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 13:01:34,354 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-07 13:01:34,354 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-07 13:01:34,354 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-07 13:01:34,355 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2022-04-07 13:01:34,355 INFO L87 Difference]: Start difference. First operand 40 states and 49 transitions. Second operand has 9 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-07 13:01:34,719 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:34,719 INFO L93 Difference]: Finished difference Result 57 states and 72 transitions. [2022-04-07 13:01:34,719 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-07 13:01:34,720 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) Word has length 33 [2022-04-07 13:01:34,720 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 13:01:34,720 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-07 13:01:34,721 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 69 transitions. [2022-04-07 13:01:34,722 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-07 13:01:34,723 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 69 transitions. [2022-04-07 13:01:34,723 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 9 states and 69 transitions. [2022-04-07 13:01:34,781 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 69 edges. 69 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 13:01:34,782 INFO L225 Difference]: With dead ends: 57 [2022-04-07 13:01:34,782 INFO L226 Difference]: Without dead ends: 54 [2022-04-07 13:01:34,783 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-04-07 13:01:34,783 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 29 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 143 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 143 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-07 13:01:34,783 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 180 Invalid, 152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 143 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-07 13:01:34,784 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-04-07 13:01:34,803 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 53. [2022-04-07 13:01:34,803 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-07 13:01:34,803 INFO L82 GeneralOperation]: Start isEquivalent. First operand 54 states. Second operand has 53 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 30 states have internal predecessors, (33), 18 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-07 13:01:34,804 INFO L74 IsIncluded]: Start isIncluded. First operand 54 states. Second operand has 53 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 30 states have internal predecessors, (33), 18 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-07 13:01:34,804 INFO L87 Difference]: Start difference. First operand 54 states. Second operand has 53 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 30 states have internal predecessors, (33), 18 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-07 13:01:34,806 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:34,806 INFO L93 Difference]: Finished difference Result 54 states and 68 transitions. [2022-04-07 13:01:34,806 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 68 transitions. [2022-04-07 13:01:34,807 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:34,807 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:34,807 INFO L74 IsIncluded]: Start isIncluded. First operand has 53 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 30 states have internal predecessors, (33), 18 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) Second operand 54 states. [2022-04-07 13:01:34,807 INFO L87 Difference]: Start difference. First operand has 53 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 30 states have internal predecessors, (33), 18 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) Second operand 54 states. [2022-04-07 13:01:34,809 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:34,809 INFO L93 Difference]: Finished difference Result 54 states and 68 transitions. [2022-04-07 13:01:34,809 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 68 transitions. [2022-04-07 13:01:34,810 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:34,810 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:34,810 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-07 13:01:34,810 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-07 13:01:34,810 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 30 states have internal predecessors, (33), 18 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-07 13:01:34,812 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 67 transitions. [2022-04-07 13:01:34,812 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 67 transitions. Word has length 33 [2022-04-07 13:01:34,815 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 13:01:34,815 INFO L478 AbstractCegarLoop]: Abstraction has 53 states and 67 transitions. [2022-04-07 13:01:34,815 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-07 13:01:34,815 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 67 transitions. [2022-04-07 13:01:34,817 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-04-07 13:01:34,817 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 13:01:34,817 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 13:01:34,835 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-07 13:01:35,024 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-07 13:01:35,024 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 13:01:35,024 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 13:01:35,024 INFO L85 PathProgramCache]: Analyzing trace with hash -1297647068, now seen corresponding path program 1 times [2022-04-07 13:01:35,025 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 13:01:35,025 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1006394316] [2022-04-07 13:01:35,025 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 13:01:35,025 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 13:01:35,041 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 13:01:35,041 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [797185982] [2022-04-07 13:01:35,042 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 13:01:35,042 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 13:01:35,042 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 13:01:35,047 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-07 13:01:35,059 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-07 13:01:35,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:35,092 INFO L263 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-07 13:01:35,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:35,102 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 13:01:35,311 INFO L272 TraceCheckUtils]: 0: Hoare triple {981#true} call ULTIMATE.init(); {981#true} is VALID [2022-04-07 13:01:35,312 INFO L290 TraceCheckUtils]: 1: Hoare triple {981#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(14, 2);call #Ultimate.allocInit(12, 3); {981#true} is VALID [2022-04-07 13:01:35,312 INFO L290 TraceCheckUtils]: 2: Hoare triple {981#true} assume true; {981#true} is VALID [2022-04-07 13:01:35,312 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {981#true} {981#true} #98#return; {981#true} is VALID [2022-04-07 13:01:35,312 INFO L272 TraceCheckUtils]: 4: Hoare triple {981#true} call #t~ret6 := main(); {981#true} is VALID [2022-04-07 13:01:35,312 INFO L290 TraceCheckUtils]: 5: Hoare triple {981#true} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4; {981#true} is VALID [2022-04-07 13:01:35,312 INFO L272 TraceCheckUtils]: 6: Hoare triple {981#true} call assume_abort_if_not((if ~x~0 >= 0 && ~x~0 <= 1 then 1 else 0)); {981#true} is VALID [2022-04-07 13:01:35,312 INFO L290 TraceCheckUtils]: 7: Hoare triple {981#true} ~cond := #in~cond; {981#true} is VALID [2022-04-07 13:01:35,312 INFO L290 TraceCheckUtils]: 8: Hoare triple {981#true} assume !(0 == ~cond); {981#true} is VALID [2022-04-07 13:01:35,312 INFO L290 TraceCheckUtils]: 9: Hoare triple {981#true} assume true; {981#true} is VALID [2022-04-07 13:01:35,313 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {981#true} {981#true} #78#return; {981#true} is VALID [2022-04-07 13:01:35,313 INFO L290 TraceCheckUtils]: 11: Hoare triple {981#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {981#true} is VALID [2022-04-07 13:01:35,313 INFO L272 TraceCheckUtils]: 12: Hoare triple {981#true} call assume_abort_if_not((if ~y~0 >= 0 && ~y~0 <= 1 then 1 else 0)); {981#true} is VALID [2022-04-07 13:01:35,314 INFO L290 TraceCheckUtils]: 13: Hoare triple {981#true} ~cond := #in~cond; {1025#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-07 13:01:35,315 INFO L290 TraceCheckUtils]: 14: Hoare triple {1025#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {1029#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:35,316 INFO L290 TraceCheckUtils]: 15: Hoare triple {1029#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {1029#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:35,328 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1029#(not (= |assume_abort_if_not_#in~cond| 0))} {981#true} #80#return; {1036#(and (<= 0 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:35,328 INFO L272 TraceCheckUtils]: 17: Hoare triple {1036#(and (<= 0 main_~y~0) (<= main_~y~0 1))} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {981#true} is VALID [2022-04-07 13:01:35,328 INFO L290 TraceCheckUtils]: 18: Hoare triple {981#true} ~cond := #in~cond; {1025#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-07 13:01:35,329 INFO L290 TraceCheckUtils]: 19: Hoare triple {1025#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {1029#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:35,329 INFO L290 TraceCheckUtils]: 20: Hoare triple {1029#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {1029#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:35,329 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {1029#(not (= |assume_abort_if_not_#in~cond| 0))} {1036#(and (<= 0 main_~y~0) (<= main_~y~0 1))} #82#return; {1052#(and (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:35,330 INFO L290 TraceCheckUtils]: 22: Hoare triple {1052#(and (<= 1 main_~y~0) (<= main_~y~0 1))} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {1052#(and (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:35,330 INFO L290 TraceCheckUtils]: 23: Hoare triple {1052#(and (<= 1 main_~y~0) (<= main_~y~0 1))} assume !false; {1052#(and (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:35,330 INFO L272 TraceCheckUtils]: 24: Hoare triple {1052#(and (<= 1 main_~y~0) (<= main_~y~0 1))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {981#true} is VALID [2022-04-07 13:01:35,330 INFO L290 TraceCheckUtils]: 25: Hoare triple {981#true} ~cond := #in~cond; {981#true} is VALID [2022-04-07 13:01:35,330 INFO L290 TraceCheckUtils]: 26: Hoare triple {981#true} assume !(0 == ~cond); {981#true} is VALID [2022-04-07 13:01:35,331 INFO L290 TraceCheckUtils]: 27: Hoare triple {981#true} assume true; {981#true} is VALID [2022-04-07 13:01:35,331 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {981#true} {1052#(and (<= 1 main_~y~0) (<= main_~y~0 1))} #84#return; {1052#(and (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:35,331 INFO L272 TraceCheckUtils]: 29: Hoare triple {1052#(and (<= 1 main_~y~0) (<= main_~y~0 1))} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {981#true} is VALID [2022-04-07 13:01:35,331 INFO L290 TraceCheckUtils]: 30: Hoare triple {981#true} ~cond := #in~cond; {981#true} is VALID [2022-04-07 13:01:35,331 INFO L290 TraceCheckUtils]: 31: Hoare triple {981#true} assume !(0 == ~cond); {981#true} is VALID [2022-04-07 13:01:35,331 INFO L290 TraceCheckUtils]: 32: Hoare triple {981#true} assume true; {981#true} is VALID [2022-04-07 13:01:35,332 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {981#true} {1052#(and (<= 1 main_~y~0) (<= main_~y~0 1))} #86#return; {1052#(and (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:35,332 INFO L290 TraceCheckUtils]: 34: Hoare triple {1052#(and (<= 1 main_~y~0) (<= main_~y~0 1))} assume !!(~r~0 >= ~y~0);~a~0 := 1;~b~0 := ~y~0; {1092#(and (= main_~a~0 1) (= main_~b~0 main_~y~0) (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:35,333 INFO L290 TraceCheckUtils]: 35: Hoare triple {1092#(and (= main_~a~0 1) (= main_~b~0 main_~y~0) (<= 1 main_~y~0) (<= main_~y~0 1))} assume !false; {1092#(and (= main_~a~0 1) (= main_~b~0 main_~y~0) (<= 1 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:35,333 INFO L272 TraceCheckUtils]: 36: Hoare triple {1092#(and (= main_~a~0 1) (= main_~b~0 main_~y~0) (<= 1 main_~y~0) (<= main_~y~0 1))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {1099#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-07 13:01:35,334 INFO L290 TraceCheckUtils]: 37: Hoare triple {1099#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1103#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-07 13:01:35,334 INFO L290 TraceCheckUtils]: 38: Hoare triple {1103#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {982#false} is VALID [2022-04-07 13:01:35,334 INFO L290 TraceCheckUtils]: 39: Hoare triple {982#false} assume !false; {982#false} is VALID [2022-04-07 13:01:35,334 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2022-04-07 13:01:35,334 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-07 13:01:35,335 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 13:01:35,335 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1006394316] [2022-04-07 13:01:35,335 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 13:01:35,335 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [797185982] [2022-04-07 13:01:35,335 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [797185982] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 13:01:35,335 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 13:01:35,335 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-07 13:01:35,335 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1008611367] [2022-04-07 13:01:35,335 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 13:01:35,335 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 40 [2022-04-07 13:01:35,336 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-07 13:01:35,336 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 9 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 13:01:35,362 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 34 edges. 34 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 13:01:35,362 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-07 13:01:35,362 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-07 13:01:35,362 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-07 13:01:35,362 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2022-04-07 13:01:35,363 INFO L87 Difference]: Start difference. First operand 53 states and 67 transitions. Second operand has 9 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 13:01:35,753 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:35,753 INFO L93 Difference]: Finished difference Result 79 states and 105 transitions. [2022-04-07 13:01:35,753 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-07 13:01:35,753 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 40 [2022-04-07 13:01:35,754 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 13:01:35,754 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 13:01:35,755 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 69 transitions. [2022-04-07 13:01:35,755 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 13:01:35,756 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 69 transitions. [2022-04-07 13:01:35,756 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 9 states and 69 transitions. [2022-04-07 13:01:35,801 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 69 edges. 69 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 13:01:35,803 INFO L225 Difference]: With dead ends: 79 [2022-04-07 13:01:35,803 INFO L226 Difference]: Without dead ends: 77 [2022-04-07 13:01:35,804 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-04-07 13:01:35,804 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 22 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 177 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 201 SdHoareTripleChecker+Invalid, 181 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 177 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-07 13:01:35,804 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 201 Invalid, 181 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 177 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-07 13:01:35,805 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2022-04-07 13:01:35,834 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 70. [2022-04-07 13:01:35,835 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-07 13:01:35,835 INFO L82 GeneralOperation]: Start isEquivalent. First operand 77 states. Second operand has 70 states, 38 states have (on average 1.1578947368421053) internal successors, (44), 40 states have internal predecessors, (44), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-07 13:01:35,835 INFO L74 IsIncluded]: Start isIncluded. First operand 77 states. Second operand has 70 states, 38 states have (on average 1.1578947368421053) internal successors, (44), 40 states have internal predecessors, (44), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-07 13:01:35,836 INFO L87 Difference]: Start difference. First operand 77 states. Second operand has 70 states, 38 states have (on average 1.1578947368421053) internal successors, (44), 40 states have internal predecessors, (44), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-07 13:01:35,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:35,838 INFO L93 Difference]: Finished difference Result 77 states and 103 transitions. [2022-04-07 13:01:35,838 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 103 transitions. [2022-04-07 13:01:35,839 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:35,839 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:35,839 INFO L74 IsIncluded]: Start isIncluded. First operand has 70 states, 38 states have (on average 1.1578947368421053) internal successors, (44), 40 states have internal predecessors, (44), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) Second operand 77 states. [2022-04-07 13:01:35,839 INFO L87 Difference]: Start difference. First operand has 70 states, 38 states have (on average 1.1578947368421053) internal successors, (44), 40 states have internal predecessors, (44), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) Second operand 77 states. [2022-04-07 13:01:35,842 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:35,842 INFO L93 Difference]: Finished difference Result 77 states and 103 transitions. [2022-04-07 13:01:35,842 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 103 transitions. [2022-04-07 13:01:35,842 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:35,842 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:35,842 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-07 13:01:35,843 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-07 13:01:35,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 38 states have (on average 1.1578947368421053) internal successors, (44), 40 states have internal predecessors, (44), 25 states have call successors, (25), 7 states have call predecessors, (25), 6 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-07 13:01:35,845 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 92 transitions. [2022-04-07 13:01:35,845 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 92 transitions. Word has length 40 [2022-04-07 13:01:35,845 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 13:01:35,845 INFO L478 AbstractCegarLoop]: Abstraction has 70 states and 92 transitions. [2022-04-07 13:01:35,845 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-07 13:01:35,845 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 92 transitions. [2022-04-07 13:01:35,846 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-04-07 13:01:35,846 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 13:01:35,846 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 13:01:35,862 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-07 13:01:36,052 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-07 13:01:36,052 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 13:01:36,052 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 13:01:36,052 INFO L85 PathProgramCache]: Analyzing trace with hash -391974204, now seen corresponding path program 1 times [2022-04-07 13:01:36,053 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 13:01:36,053 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [568911461] [2022-04-07 13:01:36,053 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 13:01:36,053 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 13:01:36,081 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 13:01:36,082 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [653322858] [2022-04-07 13:01:36,082 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 13:01:36,082 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 13:01:36,082 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 13:01:36,083 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-07 13:01:36,111 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-07 13:01:36,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:36,133 INFO L263 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-07 13:01:36,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:36,144 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 13:01:36,397 INFO L272 TraceCheckUtils]: 0: Hoare triple {1498#true} call ULTIMATE.init(); {1498#true} is VALID [2022-04-07 13:01:36,397 INFO L290 TraceCheckUtils]: 1: Hoare triple {1498#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(14, 2);call #Ultimate.allocInit(12, 3); {1498#true} is VALID [2022-04-07 13:01:36,397 INFO L290 TraceCheckUtils]: 2: Hoare triple {1498#true} assume true; {1498#true} is VALID [2022-04-07 13:01:36,397 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1498#true} {1498#true} #98#return; {1498#true} is VALID [2022-04-07 13:01:36,397 INFO L272 TraceCheckUtils]: 4: Hoare triple {1498#true} call #t~ret6 := main(); {1498#true} is VALID [2022-04-07 13:01:36,397 INFO L290 TraceCheckUtils]: 5: Hoare triple {1498#true} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4; {1498#true} is VALID [2022-04-07 13:01:36,397 INFO L272 TraceCheckUtils]: 6: Hoare triple {1498#true} call assume_abort_if_not((if ~x~0 >= 0 && ~x~0 <= 1 then 1 else 0)); {1498#true} is VALID [2022-04-07 13:01:36,398 INFO L290 TraceCheckUtils]: 7: Hoare triple {1498#true} ~cond := #in~cond; {1498#true} is VALID [2022-04-07 13:01:36,398 INFO L290 TraceCheckUtils]: 8: Hoare triple {1498#true} assume !(0 == ~cond); {1498#true} is VALID [2022-04-07 13:01:36,398 INFO L290 TraceCheckUtils]: 9: Hoare triple {1498#true} assume true; {1498#true} is VALID [2022-04-07 13:01:36,398 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1498#true} {1498#true} #78#return; {1498#true} is VALID [2022-04-07 13:01:36,398 INFO L290 TraceCheckUtils]: 11: Hoare triple {1498#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {1498#true} is VALID [2022-04-07 13:01:36,398 INFO L272 TraceCheckUtils]: 12: Hoare triple {1498#true} call assume_abort_if_not((if ~y~0 >= 0 && ~y~0 <= 1 then 1 else 0)); {1498#true} is VALID [2022-04-07 13:01:36,398 INFO L290 TraceCheckUtils]: 13: Hoare triple {1498#true} ~cond := #in~cond; {1498#true} is VALID [2022-04-07 13:01:36,398 INFO L290 TraceCheckUtils]: 14: Hoare triple {1498#true} assume !(0 == ~cond); {1498#true} is VALID [2022-04-07 13:01:36,398 INFO L290 TraceCheckUtils]: 15: Hoare triple {1498#true} assume true; {1498#true} is VALID [2022-04-07 13:01:36,398 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1498#true} {1498#true} #80#return; {1498#true} is VALID [2022-04-07 13:01:36,398 INFO L272 TraceCheckUtils]: 17: Hoare triple {1498#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1498#true} is VALID [2022-04-07 13:01:36,399 INFO L290 TraceCheckUtils]: 18: Hoare triple {1498#true} ~cond := #in~cond; {1557#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-07 13:01:36,399 INFO L290 TraceCheckUtils]: 19: Hoare triple {1557#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {1561#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:36,399 INFO L290 TraceCheckUtils]: 20: Hoare triple {1561#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {1561#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:36,400 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {1561#(not (= |assume_abort_if_not_#in~cond| 0))} {1498#true} #82#return; {1568#(<= 1 main_~y~0)} is VALID [2022-04-07 13:01:36,400 INFO L290 TraceCheckUtils]: 22: Hoare triple {1568#(<= 1 main_~y~0)} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {1568#(<= 1 main_~y~0)} is VALID [2022-04-07 13:01:36,400 INFO L290 TraceCheckUtils]: 23: Hoare triple {1568#(<= 1 main_~y~0)} assume !false; {1568#(<= 1 main_~y~0)} is VALID [2022-04-07 13:01:36,400 INFO L272 TraceCheckUtils]: 24: Hoare triple {1568#(<= 1 main_~y~0)} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {1498#true} is VALID [2022-04-07 13:01:36,400 INFO L290 TraceCheckUtils]: 25: Hoare triple {1498#true} ~cond := #in~cond; {1498#true} is VALID [2022-04-07 13:01:36,401 INFO L290 TraceCheckUtils]: 26: Hoare triple {1498#true} assume !(0 == ~cond); {1498#true} is VALID [2022-04-07 13:01:36,401 INFO L290 TraceCheckUtils]: 27: Hoare triple {1498#true} assume true; {1498#true} is VALID [2022-04-07 13:01:36,401 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {1498#true} {1568#(<= 1 main_~y~0)} #84#return; {1568#(<= 1 main_~y~0)} is VALID [2022-04-07 13:01:36,401 INFO L272 TraceCheckUtils]: 29: Hoare triple {1568#(<= 1 main_~y~0)} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {1498#true} is VALID [2022-04-07 13:01:36,401 INFO L290 TraceCheckUtils]: 30: Hoare triple {1498#true} ~cond := #in~cond; {1498#true} is VALID [2022-04-07 13:01:36,401 INFO L290 TraceCheckUtils]: 31: Hoare triple {1498#true} assume !(0 == ~cond); {1498#true} is VALID [2022-04-07 13:01:36,401 INFO L290 TraceCheckUtils]: 32: Hoare triple {1498#true} assume true; {1498#true} is VALID [2022-04-07 13:01:36,402 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {1498#true} {1568#(<= 1 main_~y~0)} #86#return; {1568#(<= 1 main_~y~0)} is VALID [2022-04-07 13:01:36,402 INFO L290 TraceCheckUtils]: 34: Hoare triple {1568#(<= 1 main_~y~0)} assume !!(~r~0 >= ~y~0);~a~0 := 1;~b~0 := ~y~0; {1608#(<= 1 main_~r~0)} is VALID [2022-04-07 13:01:36,403 INFO L290 TraceCheckUtils]: 35: Hoare triple {1608#(<= 1 main_~r~0)} assume !false; {1608#(<= 1 main_~r~0)} is VALID [2022-04-07 13:01:36,403 INFO L272 TraceCheckUtils]: 36: Hoare triple {1608#(<= 1 main_~r~0)} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {1498#true} is VALID [2022-04-07 13:01:36,403 INFO L290 TraceCheckUtils]: 37: Hoare triple {1498#true} ~cond := #in~cond; {1498#true} is VALID [2022-04-07 13:01:36,404 INFO L290 TraceCheckUtils]: 38: Hoare triple {1498#true} assume !(0 == ~cond); {1498#true} is VALID [2022-04-07 13:01:36,404 INFO L290 TraceCheckUtils]: 39: Hoare triple {1498#true} assume true; {1498#true} is VALID [2022-04-07 13:01:36,404 INFO L284 TraceCheckUtils]: 40: Hoare quadruple {1498#true} {1608#(<= 1 main_~r~0)} #88#return; {1608#(<= 1 main_~r~0)} is VALID [2022-04-07 13:01:36,404 INFO L272 TraceCheckUtils]: 41: Hoare triple {1608#(<= 1 main_~r~0)} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {1498#true} is VALID [2022-04-07 13:01:36,404 INFO L290 TraceCheckUtils]: 42: Hoare triple {1498#true} ~cond := #in~cond; {1498#true} is VALID [2022-04-07 13:01:36,404 INFO L290 TraceCheckUtils]: 43: Hoare triple {1498#true} assume !(0 == ~cond); {1498#true} is VALID [2022-04-07 13:01:36,404 INFO L290 TraceCheckUtils]: 44: Hoare triple {1498#true} assume true; {1498#true} is VALID [2022-04-07 13:01:36,405 INFO L284 TraceCheckUtils]: 45: Hoare quadruple {1498#true} {1608#(<= 1 main_~r~0)} #90#return; {1608#(<= 1 main_~r~0)} is VALID [2022-04-07 13:01:36,405 INFO L272 TraceCheckUtils]: 46: Hoare triple {1608#(<= 1 main_~r~0)} call __VERIFIER_assert((if ~r~0 >= 0 then 1 else 0)); {1645#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-07 13:01:36,406 INFO L290 TraceCheckUtils]: 47: Hoare triple {1645#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1649#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-07 13:01:36,406 INFO L290 TraceCheckUtils]: 48: Hoare triple {1649#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1499#false} is VALID [2022-04-07 13:01:36,406 INFO L290 TraceCheckUtils]: 49: Hoare triple {1499#false} assume !false; {1499#false} is VALID [2022-04-07 13:01:36,406 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-04-07 13:01:36,406 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-07 13:01:36,407 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 13:01:36,407 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [568911461] [2022-04-07 13:01:36,407 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 13:01:36,407 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [653322858] [2022-04-07 13:01:36,407 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [653322858] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-07 13:01:36,407 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-07 13:01:36,407 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-07 13:01:36,407 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [230780259] [2022-04-07 13:01:36,407 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-07 13:01:36,407 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 50 [2022-04-07 13:01:36,408 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-07 13:01:36,408 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-07 13:01:36,437 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 38 edges. 38 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 13:01:36,437 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-07 13:01:36,437 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-07 13:01:36,437 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-07 13:01:36,437 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2022-04-07 13:01:36,438 INFO L87 Difference]: Start difference. First operand 70 states and 92 transitions. Second operand has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-07 13:01:36,740 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:36,740 INFO L93 Difference]: Finished difference Result 76 states and 97 transitions. [2022-04-07 13:01:36,740 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-07 13:01:36,741 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 50 [2022-04-07 13:01:36,741 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 13:01:36,742 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-07 13:01:36,743 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 48 transitions. [2022-04-07 13:01:36,743 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-07 13:01:36,744 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 48 transitions. [2022-04-07 13:01:36,744 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 48 transitions. [2022-04-07 13:01:36,775 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 48 edges. 48 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 13:01:36,778 INFO L225 Difference]: With dead ends: 76 [2022-04-07 13:01:36,778 INFO L226 Difference]: Without dead ends: 74 [2022-04-07 13:01:36,778 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-04-07 13:01:36,779 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 16 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 125 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 132 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 125 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-07 13:01:36,779 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 160 Invalid, 132 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 125 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-07 13:01:36,779 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2022-04-07 13:01:36,828 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 74. [2022-04-07 13:01:36,829 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-07 13:01:36,829 INFO L82 GeneralOperation]: Start isEquivalent. First operand 74 states. Second operand has 74 states, 41 states have (on average 1.146341463414634) internal successors, (47), 43 states have internal predecessors, (47), 25 states have call successors, (25), 8 states have call predecessors, (25), 7 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-07 13:01:36,829 INFO L74 IsIncluded]: Start isIncluded. First operand 74 states. Second operand has 74 states, 41 states have (on average 1.146341463414634) internal successors, (47), 43 states have internal predecessors, (47), 25 states have call successors, (25), 8 states have call predecessors, (25), 7 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-07 13:01:36,829 INFO L87 Difference]: Start difference. First operand 74 states. Second operand has 74 states, 41 states have (on average 1.146341463414634) internal successors, (47), 43 states have internal predecessors, (47), 25 states have call successors, (25), 8 states have call predecessors, (25), 7 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-07 13:01:36,832 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:36,832 INFO L93 Difference]: Finished difference Result 74 states and 95 transitions. [2022-04-07 13:01:36,832 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 95 transitions. [2022-04-07 13:01:36,832 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:36,832 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:36,832 INFO L74 IsIncluded]: Start isIncluded. First operand has 74 states, 41 states have (on average 1.146341463414634) internal successors, (47), 43 states have internal predecessors, (47), 25 states have call successors, (25), 8 states have call predecessors, (25), 7 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) Second operand 74 states. [2022-04-07 13:01:36,832 INFO L87 Difference]: Start difference. First operand has 74 states, 41 states have (on average 1.146341463414634) internal successors, (47), 43 states have internal predecessors, (47), 25 states have call successors, (25), 8 states have call predecessors, (25), 7 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) Second operand 74 states. [2022-04-07 13:01:36,835 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:36,835 INFO L93 Difference]: Finished difference Result 74 states and 95 transitions. [2022-04-07 13:01:36,835 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 95 transitions. [2022-04-07 13:01:36,835 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:36,835 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:36,835 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-07 13:01:36,835 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-07 13:01:36,835 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 41 states have (on average 1.146341463414634) internal successors, (47), 43 states have internal predecessors, (47), 25 states have call successors, (25), 8 states have call predecessors, (25), 7 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-07 13:01:36,837 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 95 transitions. [2022-04-07 13:01:36,837 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 95 transitions. Word has length 50 [2022-04-07 13:01:36,837 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 13:01:36,837 INFO L478 AbstractCegarLoop]: Abstraction has 74 states and 95 transitions. [2022-04-07 13:01:36,838 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.5) internal successors, (20), 7 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-07 13:01:36,838 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 95 transitions. [2022-04-07 13:01:36,838 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-04-07 13:01:36,838 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 13:01:36,838 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 13:01:36,856 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-07 13:01:37,043 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-07 13:01:37,043 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 13:01:37,044 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 13:01:37,044 INFO L85 PathProgramCache]: Analyzing trace with hash 991781023, now seen corresponding path program 1 times [2022-04-07 13:01:37,044 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 13:01:37,044 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1984335880] [2022-04-07 13:01:37,044 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 13:01:37,044 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 13:01:37,057 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 13:01:37,057 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [88818493] [2022-04-07 13:01:37,057 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 13:01:37,057 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 13:01:37,058 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 13:01:37,058 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-07 13:01:37,059 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-07 13:01:37,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:37,094 INFO L263 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-07 13:01:37,109 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:37,111 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 13:01:37,417 INFO L272 TraceCheckUtils]: 0: Hoare triple {2039#true} call ULTIMATE.init(); {2039#true} is VALID [2022-04-07 13:01:37,417 INFO L290 TraceCheckUtils]: 1: Hoare triple {2039#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(14, 2);call #Ultimate.allocInit(12, 3); {2039#true} is VALID [2022-04-07 13:01:37,417 INFO L290 TraceCheckUtils]: 2: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:37,417 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2039#true} {2039#true} #98#return; {2039#true} is VALID [2022-04-07 13:01:37,417 INFO L272 TraceCheckUtils]: 4: Hoare triple {2039#true} call #t~ret6 := main(); {2039#true} is VALID [2022-04-07 13:01:37,417 INFO L290 TraceCheckUtils]: 5: Hoare triple {2039#true} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4; {2039#true} is VALID [2022-04-07 13:01:37,417 INFO L272 TraceCheckUtils]: 6: Hoare triple {2039#true} call assume_abort_if_not((if ~x~0 >= 0 && ~x~0 <= 1 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:37,418 INFO L290 TraceCheckUtils]: 7: Hoare triple {2039#true} ~cond := #in~cond; {2065#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-07 13:01:37,418 INFO L290 TraceCheckUtils]: 8: Hoare triple {2065#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {2069#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:37,418 INFO L290 TraceCheckUtils]: 9: Hoare triple {2069#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {2069#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:37,419 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2069#(not (= |assume_abort_if_not_#in~cond| 0))} {2039#true} #78#return; {2076#(and (<= 0 main_~x~0) (<= main_~x~0 1))} is VALID [2022-04-07 13:01:37,419 INFO L290 TraceCheckUtils]: 11: Hoare triple {2076#(and (<= 0 main_~x~0) (<= main_~x~0 1))} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {2076#(and (<= 0 main_~x~0) (<= main_~x~0 1))} is VALID [2022-04-07 13:01:37,419 INFO L272 TraceCheckUtils]: 12: Hoare triple {2076#(and (<= 0 main_~x~0) (<= main_~x~0 1))} call assume_abort_if_not((if ~y~0 >= 0 && ~y~0 <= 1 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:37,419 INFO L290 TraceCheckUtils]: 13: Hoare triple {2039#true} ~cond := #in~cond; {2039#true} is VALID [2022-04-07 13:01:37,419 INFO L290 TraceCheckUtils]: 14: Hoare triple {2039#true} assume !(0 == ~cond); {2039#true} is VALID [2022-04-07 13:01:37,420 INFO L290 TraceCheckUtils]: 15: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:37,420 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {2039#true} {2076#(and (<= 0 main_~x~0) (<= main_~x~0 1))} #80#return; {2076#(and (<= 0 main_~x~0) (<= main_~x~0 1))} is VALID [2022-04-07 13:01:37,420 INFO L272 TraceCheckUtils]: 17: Hoare triple {2076#(and (<= 0 main_~x~0) (<= main_~x~0 1))} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:37,420 INFO L290 TraceCheckUtils]: 18: Hoare triple {2039#true} ~cond := #in~cond; {2065#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-07 13:01:37,421 INFO L290 TraceCheckUtils]: 19: Hoare triple {2065#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {2069#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:37,421 INFO L290 TraceCheckUtils]: 20: Hoare triple {2069#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {2069#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:37,422 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {2069#(not (= |assume_abort_if_not_#in~cond| 0))} {2076#(and (<= 0 main_~x~0) (<= main_~x~0 1))} #82#return; {2110#(and (<= 0 main_~x~0) (<= main_~x~0 1) (<= 1 main_~y~0))} is VALID [2022-04-07 13:01:37,422 INFO L290 TraceCheckUtils]: 22: Hoare triple {2110#(and (<= 0 main_~x~0) (<= main_~x~0 1) (<= 1 main_~y~0))} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {2114#(and (<= main_~r~0 1) (<= 1 main_~y~0))} is VALID [2022-04-07 13:01:37,422 INFO L290 TraceCheckUtils]: 23: Hoare triple {2114#(and (<= main_~r~0 1) (<= 1 main_~y~0))} assume !false; {2114#(and (<= main_~r~0 1) (<= 1 main_~y~0))} is VALID [2022-04-07 13:01:37,422 INFO L272 TraceCheckUtils]: 24: Hoare triple {2114#(and (<= main_~r~0 1) (<= 1 main_~y~0))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:37,422 INFO L290 TraceCheckUtils]: 25: Hoare triple {2039#true} ~cond := #in~cond; {2039#true} is VALID [2022-04-07 13:01:37,422 INFO L290 TraceCheckUtils]: 26: Hoare triple {2039#true} assume !(0 == ~cond); {2039#true} is VALID [2022-04-07 13:01:37,423 INFO L290 TraceCheckUtils]: 27: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:37,423 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {2039#true} {2114#(and (<= main_~r~0 1) (<= 1 main_~y~0))} #84#return; {2114#(and (<= main_~r~0 1) (<= 1 main_~y~0))} is VALID [2022-04-07 13:01:37,423 INFO L272 TraceCheckUtils]: 29: Hoare triple {2114#(and (<= main_~r~0 1) (<= 1 main_~y~0))} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:37,423 INFO L290 TraceCheckUtils]: 30: Hoare triple {2039#true} ~cond := #in~cond; {2039#true} is VALID [2022-04-07 13:01:37,423 INFO L290 TraceCheckUtils]: 31: Hoare triple {2039#true} assume !(0 == ~cond); {2039#true} is VALID [2022-04-07 13:01:37,423 INFO L290 TraceCheckUtils]: 32: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:37,424 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {2039#true} {2114#(and (<= main_~r~0 1) (<= 1 main_~y~0))} #86#return; {2114#(and (<= main_~r~0 1) (<= 1 main_~y~0))} is VALID [2022-04-07 13:01:37,424 INFO L290 TraceCheckUtils]: 34: Hoare triple {2114#(and (<= main_~r~0 1) (<= 1 main_~y~0))} assume !!(~r~0 >= ~y~0);~a~0 := 1;~b~0 := ~y~0; {2151#(and (<= main_~r~0 1) (<= 1 main_~b~0))} is VALID [2022-04-07 13:01:37,425 INFO L290 TraceCheckUtils]: 35: Hoare triple {2151#(and (<= main_~r~0 1) (<= 1 main_~b~0))} assume !false; {2151#(and (<= main_~r~0 1) (<= 1 main_~b~0))} is VALID [2022-04-07 13:01:37,425 INFO L272 TraceCheckUtils]: 36: Hoare triple {2151#(and (<= main_~r~0 1) (<= 1 main_~b~0))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:37,425 INFO L290 TraceCheckUtils]: 37: Hoare triple {2039#true} ~cond := #in~cond; {2039#true} is VALID [2022-04-07 13:01:37,425 INFO L290 TraceCheckUtils]: 38: Hoare triple {2039#true} assume !(0 == ~cond); {2039#true} is VALID [2022-04-07 13:01:37,425 INFO L290 TraceCheckUtils]: 39: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:37,425 INFO L284 TraceCheckUtils]: 40: Hoare quadruple {2039#true} {2151#(and (<= main_~r~0 1) (<= 1 main_~b~0))} #88#return; {2151#(and (<= main_~r~0 1) (<= 1 main_~b~0))} is VALID [2022-04-07 13:01:37,426 INFO L272 TraceCheckUtils]: 41: Hoare triple {2151#(and (<= main_~r~0 1) (<= 1 main_~b~0))} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:37,426 INFO L290 TraceCheckUtils]: 42: Hoare triple {2039#true} ~cond := #in~cond; {2039#true} is VALID [2022-04-07 13:01:37,426 INFO L290 TraceCheckUtils]: 43: Hoare triple {2039#true} assume !(0 == ~cond); {2039#true} is VALID [2022-04-07 13:01:37,426 INFO L290 TraceCheckUtils]: 44: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:37,426 INFO L284 TraceCheckUtils]: 45: Hoare quadruple {2039#true} {2151#(and (<= main_~r~0 1) (<= 1 main_~b~0))} #90#return; {2151#(and (<= main_~r~0 1) (<= 1 main_~b~0))} is VALID [2022-04-07 13:01:37,426 INFO L272 TraceCheckUtils]: 46: Hoare triple {2151#(and (<= main_~r~0 1) (<= 1 main_~b~0))} call __VERIFIER_assert((if ~r~0 >= 0 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:37,426 INFO L290 TraceCheckUtils]: 47: Hoare triple {2039#true} ~cond := #in~cond; {2039#true} is VALID [2022-04-07 13:01:37,426 INFO L290 TraceCheckUtils]: 48: Hoare triple {2039#true} assume !(0 == ~cond); {2039#true} is VALID [2022-04-07 13:01:37,427 INFO L290 TraceCheckUtils]: 49: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:37,427 INFO L284 TraceCheckUtils]: 50: Hoare quadruple {2039#true} {2151#(and (<= main_~r~0 1) (<= 1 main_~b~0))} #92#return; {2151#(and (<= main_~r~0 1) (<= 1 main_~b~0))} is VALID [2022-04-07 13:01:37,427 INFO L290 TraceCheckUtils]: 51: Hoare triple {2151#(and (<= main_~r~0 1) (<= 1 main_~b~0))} assume !!(~r~0 >= 2 * ~b~0); {2040#false} is VALID [2022-04-07 13:01:37,428 INFO L272 TraceCheckUtils]: 52: Hoare triple {2040#false} call __VERIFIER_assert((if ~r~0 >= 2 * ~y~0 * ~a~0 then 1 else 0)); {2040#false} is VALID [2022-04-07 13:01:37,428 INFO L290 TraceCheckUtils]: 53: Hoare triple {2040#false} ~cond := #in~cond; {2040#false} is VALID [2022-04-07 13:01:37,428 INFO L290 TraceCheckUtils]: 54: Hoare triple {2040#false} assume 0 == ~cond; {2040#false} is VALID [2022-04-07 13:01:37,428 INFO L290 TraceCheckUtils]: 55: Hoare triple {2040#false} assume !false; {2040#false} is VALID [2022-04-07 13:01:37,428 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 13 proven. 3 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2022-04-07 13:01:37,428 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 13:01:38,356 INFO L290 TraceCheckUtils]: 55: Hoare triple {2040#false} assume !false; {2040#false} is VALID [2022-04-07 13:01:38,357 INFO L290 TraceCheckUtils]: 54: Hoare triple {2040#false} assume 0 == ~cond; {2040#false} is VALID [2022-04-07 13:01:38,357 INFO L290 TraceCheckUtils]: 53: Hoare triple {2040#false} ~cond := #in~cond; {2040#false} is VALID [2022-04-07 13:01:38,357 INFO L272 TraceCheckUtils]: 52: Hoare triple {2040#false} call __VERIFIER_assert((if ~r~0 >= 2 * ~y~0 * ~a~0 then 1 else 0)); {2040#false} is VALID [2022-04-07 13:01:38,358 INFO L290 TraceCheckUtils]: 51: Hoare triple {2227#(not (<= (* main_~b~0 2) main_~r~0))} assume !!(~r~0 >= 2 * ~b~0); {2040#false} is VALID [2022-04-07 13:01:38,363 INFO L284 TraceCheckUtils]: 50: Hoare quadruple {2039#true} {2227#(not (<= (* main_~b~0 2) main_~r~0))} #92#return; {2227#(not (<= (* main_~b~0 2) main_~r~0))} is VALID [2022-04-07 13:01:38,363 INFO L290 TraceCheckUtils]: 49: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:38,363 INFO L290 TraceCheckUtils]: 48: Hoare triple {2039#true} assume !(0 == ~cond); {2039#true} is VALID [2022-04-07 13:01:38,363 INFO L290 TraceCheckUtils]: 47: Hoare triple {2039#true} ~cond := #in~cond; {2039#true} is VALID [2022-04-07 13:01:38,363 INFO L272 TraceCheckUtils]: 46: Hoare triple {2227#(not (<= (* main_~b~0 2) main_~r~0))} call __VERIFIER_assert((if ~r~0 >= 0 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:38,364 INFO L284 TraceCheckUtils]: 45: Hoare quadruple {2039#true} {2227#(not (<= (* main_~b~0 2) main_~r~0))} #90#return; {2227#(not (<= (* main_~b~0 2) main_~r~0))} is VALID [2022-04-07 13:01:38,364 INFO L290 TraceCheckUtils]: 44: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:38,364 INFO L290 TraceCheckUtils]: 43: Hoare triple {2039#true} assume !(0 == ~cond); {2039#true} is VALID [2022-04-07 13:01:38,364 INFO L290 TraceCheckUtils]: 42: Hoare triple {2039#true} ~cond := #in~cond; {2039#true} is VALID [2022-04-07 13:01:38,364 INFO L272 TraceCheckUtils]: 41: Hoare triple {2227#(not (<= (* main_~b~0 2) main_~r~0))} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:38,365 INFO L284 TraceCheckUtils]: 40: Hoare quadruple {2039#true} {2227#(not (<= (* main_~b~0 2) main_~r~0))} #88#return; {2227#(not (<= (* main_~b~0 2) main_~r~0))} is VALID [2022-04-07 13:01:38,365 INFO L290 TraceCheckUtils]: 39: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:38,365 INFO L290 TraceCheckUtils]: 38: Hoare triple {2039#true} assume !(0 == ~cond); {2039#true} is VALID [2022-04-07 13:01:38,365 INFO L290 TraceCheckUtils]: 37: Hoare triple {2039#true} ~cond := #in~cond; {2039#true} is VALID [2022-04-07 13:01:38,365 INFO L272 TraceCheckUtils]: 36: Hoare triple {2227#(not (<= (* main_~b~0 2) main_~r~0))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:38,365 INFO L290 TraceCheckUtils]: 35: Hoare triple {2227#(not (<= (* main_~b~0 2) main_~r~0))} assume !false; {2227#(not (<= (* main_~b~0 2) main_~r~0))} is VALID [2022-04-07 13:01:38,366 INFO L290 TraceCheckUtils]: 34: Hoare triple {2279#(< (div main_~r~0 2) main_~y~0)} assume !!(~r~0 >= ~y~0);~a~0 := 1;~b~0 := ~y~0; {2227#(not (<= (* main_~b~0 2) main_~r~0))} is VALID [2022-04-07 13:01:38,366 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {2039#true} {2279#(< (div main_~r~0 2) main_~y~0)} #86#return; {2279#(< (div main_~r~0 2) main_~y~0)} is VALID [2022-04-07 13:01:38,366 INFO L290 TraceCheckUtils]: 32: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:38,366 INFO L290 TraceCheckUtils]: 31: Hoare triple {2039#true} assume !(0 == ~cond); {2039#true} is VALID [2022-04-07 13:01:38,366 INFO L290 TraceCheckUtils]: 30: Hoare triple {2039#true} ~cond := #in~cond; {2039#true} is VALID [2022-04-07 13:01:38,366 INFO L272 TraceCheckUtils]: 29: Hoare triple {2279#(< (div main_~r~0 2) main_~y~0)} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:38,367 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {2039#true} {2279#(< (div main_~r~0 2) main_~y~0)} #84#return; {2279#(< (div main_~r~0 2) main_~y~0)} is VALID [2022-04-07 13:01:38,367 INFO L290 TraceCheckUtils]: 27: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:38,367 INFO L290 TraceCheckUtils]: 26: Hoare triple {2039#true} assume !(0 == ~cond); {2039#true} is VALID [2022-04-07 13:01:38,367 INFO L290 TraceCheckUtils]: 25: Hoare triple {2039#true} ~cond := #in~cond; {2039#true} is VALID [2022-04-07 13:01:38,367 INFO L272 TraceCheckUtils]: 24: Hoare triple {2279#(< (div main_~r~0 2) main_~y~0)} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:38,368 INFO L290 TraceCheckUtils]: 23: Hoare triple {2279#(< (div main_~r~0 2) main_~y~0)} assume !false; {2279#(< (div main_~r~0 2) main_~y~0)} is VALID [2022-04-07 13:01:38,368 INFO L290 TraceCheckUtils]: 22: Hoare triple {2316#(< (div (+ (- 1) (* (- 1) main_~x~0)) (- 2)) (+ main_~y~0 1))} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {2279#(< (div main_~r~0 2) main_~y~0)} is VALID [2022-04-07 13:01:38,369 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {2069#(not (= |assume_abort_if_not_#in~cond| 0))} {2320#(< (div (+ (- 1) (* (- 1) main_~x~0)) (- 2)) 2)} #82#return; {2316#(< (div (+ (- 1) (* (- 1) main_~x~0)) (- 2)) (+ main_~y~0 1))} is VALID [2022-04-07 13:01:38,369 INFO L290 TraceCheckUtils]: 20: Hoare triple {2069#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {2069#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:38,370 INFO L290 TraceCheckUtils]: 19: Hoare triple {2330#(or (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond 0))} assume !(0 == ~cond); {2069#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:38,370 INFO L290 TraceCheckUtils]: 18: Hoare triple {2039#true} ~cond := #in~cond; {2330#(or (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond 0))} is VALID [2022-04-07 13:01:38,370 INFO L272 TraceCheckUtils]: 17: Hoare triple {2320#(< (div (+ (- 1) (* (- 1) main_~x~0)) (- 2)) 2)} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:38,370 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {2039#true} {2320#(< (div (+ (- 1) (* (- 1) main_~x~0)) (- 2)) 2)} #80#return; {2320#(< (div (+ (- 1) (* (- 1) main_~x~0)) (- 2)) 2)} is VALID [2022-04-07 13:01:38,371 INFO L290 TraceCheckUtils]: 15: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:38,371 INFO L290 TraceCheckUtils]: 14: Hoare triple {2039#true} assume !(0 == ~cond); {2039#true} is VALID [2022-04-07 13:01:38,371 INFO L290 TraceCheckUtils]: 13: Hoare triple {2039#true} ~cond := #in~cond; {2039#true} is VALID [2022-04-07 13:01:38,371 INFO L272 TraceCheckUtils]: 12: Hoare triple {2320#(< (div (+ (- 1) (* (- 1) main_~x~0)) (- 2)) 2)} call assume_abort_if_not((if ~y~0 >= 0 && ~y~0 <= 1 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:38,371 INFO L290 TraceCheckUtils]: 11: Hoare triple {2320#(< (div (+ (- 1) (* (- 1) main_~x~0)) (- 2)) 2)} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {2320#(< (div (+ (- 1) (* (- 1) main_~x~0)) (- 2)) 2)} is VALID [2022-04-07 13:01:38,372 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2069#(not (= |assume_abort_if_not_#in~cond| 0))} {2039#true} #78#return; {2320#(< (div (+ (- 1) (* (- 1) main_~x~0)) (- 2)) 2)} is VALID [2022-04-07 13:01:38,372 INFO L290 TraceCheckUtils]: 9: Hoare triple {2069#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {2069#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:38,372 INFO L290 TraceCheckUtils]: 8: Hoare triple {2330#(or (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond 0))} assume !(0 == ~cond); {2069#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:38,372 INFO L290 TraceCheckUtils]: 7: Hoare triple {2039#true} ~cond := #in~cond; {2330#(or (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond 0))} is VALID [2022-04-07 13:01:38,373 INFO L272 TraceCheckUtils]: 6: Hoare triple {2039#true} call assume_abort_if_not((if ~x~0 >= 0 && ~x~0 <= 1 then 1 else 0)); {2039#true} is VALID [2022-04-07 13:01:38,373 INFO L290 TraceCheckUtils]: 5: Hoare triple {2039#true} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4; {2039#true} is VALID [2022-04-07 13:01:38,373 INFO L272 TraceCheckUtils]: 4: Hoare triple {2039#true} call #t~ret6 := main(); {2039#true} is VALID [2022-04-07 13:01:38,373 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2039#true} {2039#true} #98#return; {2039#true} is VALID [2022-04-07 13:01:38,373 INFO L290 TraceCheckUtils]: 2: Hoare triple {2039#true} assume true; {2039#true} is VALID [2022-04-07 13:01:38,373 INFO L290 TraceCheckUtils]: 1: Hoare triple {2039#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(14, 2);call #Ultimate.allocInit(12, 3); {2039#true} is VALID [2022-04-07 13:01:38,373 INFO L272 TraceCheckUtils]: 0: Hoare triple {2039#true} call ULTIMATE.init(); {2039#true} is VALID [2022-04-07 13:01:38,373 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 13 proven. 3 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2022-04-07 13:01:38,373 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 13:01:38,373 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1984335880] [2022-04-07 13:01:38,373 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 13:01:38,373 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [88818493] [2022-04-07 13:01:38,374 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [88818493] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-07 13:01:38,374 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-07 13:01:38,374 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2022-04-07 13:01:38,374 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [627473498] [2022-04-07 13:01:38,374 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-07 13:01:38,374 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 9 states have call predecessors, (17), 7 states have call successors, (17) Word has length 56 [2022-04-07 13:01:38,375 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-07 13:01:38,375 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 9 states have call predecessors, (17), 7 states have call successors, (17) [2022-04-07 13:01:38,419 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-07 13:01:38,419 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-07 13:01:38,419 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-07 13:01:38,420 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-07 13:01:38,420 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2022-04-07 13:01:38,420 INFO L87 Difference]: Start difference. First operand 74 states and 95 transitions. Second operand has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 9 states have call predecessors, (17), 7 states have call successors, (17) [2022-04-07 13:01:38,875 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:38,876 INFO L93 Difference]: Finished difference Result 103 states and 127 transitions. [2022-04-07 13:01:38,876 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-07 13:01:38,876 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 9 states have call predecessors, (17), 7 states have call successors, (17) Word has length 56 [2022-04-07 13:01:38,876 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 13:01:38,876 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 9 states have call predecessors, (17), 7 states have call successors, (17) [2022-04-07 13:01:38,877 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 72 transitions. [2022-04-07 13:01:38,877 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 9 states have call predecessors, (17), 7 states have call successors, (17) [2022-04-07 13:01:38,878 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 72 transitions. [2022-04-07 13:01:38,879 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 72 transitions. [2022-04-07 13:01:38,930 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 72 edges. 72 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 13:01:38,931 INFO L225 Difference]: With dead ends: 103 [2022-04-07 13:01:38,931 INFO L226 Difference]: Without dead ends: 57 [2022-04-07 13:01:38,931 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 100 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=55, Invalid=185, Unknown=0, NotChecked=0, Total=240 [2022-04-07 13:01:38,932 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 25 mSDsluCounter, 153 mSDsCounter, 0 mSdLazyCounter, 160 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 188 SdHoareTripleChecker+Invalid, 187 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 160 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-07 13:01:38,932 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [26 Valid, 188 Invalid, 187 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 160 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-07 13:01:38,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2022-04-07 13:01:39,008 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 55. [2022-04-07 13:01:39,008 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-07 13:01:39,009 INFO L82 GeneralOperation]: Start isEquivalent. First operand 57 states. Second operand has 55 states, 32 states have (on average 1.0625) internal successors, (34), 34 states have internal predecessors, (34), 15 states have call successors, (15), 8 states have call predecessors, (15), 7 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-07 13:01:39,009 INFO L74 IsIncluded]: Start isIncluded. First operand 57 states. Second operand has 55 states, 32 states have (on average 1.0625) internal successors, (34), 34 states have internal predecessors, (34), 15 states have call successors, (15), 8 states have call predecessors, (15), 7 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-07 13:01:39,009 INFO L87 Difference]: Start difference. First operand 57 states. Second operand has 55 states, 32 states have (on average 1.0625) internal successors, (34), 34 states have internal predecessors, (34), 15 states have call successors, (15), 8 states have call predecessors, (15), 7 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-07 13:01:39,012 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:39,012 INFO L93 Difference]: Finished difference Result 57 states and 65 transitions. [2022-04-07 13:01:39,012 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 65 transitions. [2022-04-07 13:01:39,012 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:39,012 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:39,012 INFO L74 IsIncluded]: Start isIncluded. First operand has 55 states, 32 states have (on average 1.0625) internal successors, (34), 34 states have internal predecessors, (34), 15 states have call successors, (15), 8 states have call predecessors, (15), 7 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 57 states. [2022-04-07 13:01:39,012 INFO L87 Difference]: Start difference. First operand has 55 states, 32 states have (on average 1.0625) internal successors, (34), 34 states have internal predecessors, (34), 15 states have call successors, (15), 8 states have call predecessors, (15), 7 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 57 states. [2022-04-07 13:01:39,014 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:39,014 INFO L93 Difference]: Finished difference Result 57 states and 65 transitions. [2022-04-07 13:01:39,014 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 65 transitions. [2022-04-07 13:01:39,014 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:39,014 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:39,014 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-07 13:01:39,014 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-07 13:01:39,014 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 32 states have (on average 1.0625) internal successors, (34), 34 states have internal predecessors, (34), 15 states have call successors, (15), 8 states have call predecessors, (15), 7 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-07 13:01:39,015 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 62 transitions. [2022-04-07 13:01:39,015 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 62 transitions. Word has length 56 [2022-04-07 13:01:39,016 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 13:01:39,016 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 62 transitions. [2022-04-07 13:01:39,016 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 11 states have internal predecessors, (29), 8 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (17), 9 states have call predecessors, (17), 7 states have call successors, (17) [2022-04-07 13:01:39,016 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 62 transitions. [2022-04-07 13:01:39,017 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2022-04-07 13:01:39,017 INFO L491 BasicCegarLoop]: Found error trace [2022-04-07 13:01:39,017 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-07 13:01:39,039 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-07 13:01:39,240 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-07 13:01:39,240 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-07 13:01:39,240 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-07 13:01:39,240 INFO L85 PathProgramCache]: Analyzing trace with hash -2096667334, now seen corresponding path program 1 times [2022-04-07 13:01:39,240 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-07 13:01:39,240 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1397880018] [2022-04-07 13:01:39,240 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 13:01:39,241 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-07 13:01:39,262 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-07 13:01:39,262 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [894913361] [2022-04-07 13:01:39,262 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-07 13:01:39,262 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-07 13:01:39,262 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-07 13:01:39,263 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-07 13:01:39,264 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-07 13:01:39,300 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:39,300 INFO L263 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 21 conjunts are in the unsatisfiable core [2022-04-07 13:01:39,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-07 13:01:39,312 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-07 13:01:40,195 INFO L272 TraceCheckUtils]: 0: Hoare triple {2744#true} call ULTIMATE.init(); {2744#true} is VALID [2022-04-07 13:01:40,195 INFO L290 TraceCheckUtils]: 1: Hoare triple {2744#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(14, 2);call #Ultimate.allocInit(12, 3); {2744#true} is VALID [2022-04-07 13:01:40,196 INFO L290 TraceCheckUtils]: 2: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:40,196 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2744#true} {2744#true} #98#return; {2744#true} is VALID [2022-04-07 13:01:40,196 INFO L272 TraceCheckUtils]: 4: Hoare triple {2744#true} call #t~ret6 := main(); {2744#true} is VALID [2022-04-07 13:01:40,196 INFO L290 TraceCheckUtils]: 5: Hoare triple {2744#true} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4; {2744#true} is VALID [2022-04-07 13:01:40,196 INFO L272 TraceCheckUtils]: 6: Hoare triple {2744#true} call assume_abort_if_not((if ~x~0 >= 0 && ~x~0 <= 1 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:40,196 INFO L290 TraceCheckUtils]: 7: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:40,196 INFO L290 TraceCheckUtils]: 8: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:40,196 INFO L290 TraceCheckUtils]: 9: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:40,196 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2744#true} {2744#true} #78#return; {2744#true} is VALID [2022-04-07 13:01:40,196 INFO L290 TraceCheckUtils]: 11: Hoare triple {2744#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {2744#true} is VALID [2022-04-07 13:01:40,196 INFO L272 TraceCheckUtils]: 12: Hoare triple {2744#true} call assume_abort_if_not((if ~y~0 >= 0 && ~y~0 <= 1 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:40,196 INFO L290 TraceCheckUtils]: 13: Hoare triple {2744#true} ~cond := #in~cond; {2788#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-07 13:01:40,197 INFO L290 TraceCheckUtils]: 14: Hoare triple {2788#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {2792#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:40,197 INFO L290 TraceCheckUtils]: 15: Hoare triple {2792#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {2792#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:40,197 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {2792#(not (= |assume_abort_if_not_#in~cond| 0))} {2744#true} #80#return; {2799#(and (<= 0 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:40,197 INFO L272 TraceCheckUtils]: 17: Hoare triple {2799#(and (<= 0 main_~y~0) (<= main_~y~0 1))} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:40,198 INFO L290 TraceCheckUtils]: 18: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:40,198 INFO L290 TraceCheckUtils]: 19: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:40,198 INFO L290 TraceCheckUtils]: 20: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:40,200 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {2744#true} {2799#(and (<= 0 main_~y~0) (<= main_~y~0 1))} #82#return; {2799#(and (<= 0 main_~y~0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:40,200 INFO L290 TraceCheckUtils]: 22: Hoare triple {2799#(and (<= 0 main_~y~0) (<= main_~y~0 1))} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {2818#(and (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:40,201 INFO L290 TraceCheckUtils]: 23: Hoare triple {2818#(and (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= main_~y~0 1))} assume !false; {2818#(and (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:40,201 INFO L272 TraceCheckUtils]: 24: Hoare triple {2818#(and (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= main_~y~0 1))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:40,201 INFO L290 TraceCheckUtils]: 25: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:40,201 INFO L290 TraceCheckUtils]: 26: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:40,201 INFO L290 TraceCheckUtils]: 27: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:40,201 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {2744#true} {2818#(and (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= main_~y~0 1))} #84#return; {2818#(and (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:40,201 INFO L272 TraceCheckUtils]: 29: Hoare triple {2818#(and (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= main_~y~0 1))} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:40,202 INFO L290 TraceCheckUtils]: 30: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:40,202 INFO L290 TraceCheckUtils]: 31: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:40,202 INFO L290 TraceCheckUtils]: 32: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:40,206 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {2744#true} {2818#(and (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= main_~y~0 1))} #86#return; {2818#(and (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:40,206 INFO L290 TraceCheckUtils]: 34: Hoare triple {2818#(and (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= main_~y~0 1))} assume !!(~r~0 >= ~y~0);~a~0 := 1;~b~0 := ~y~0; {2855#(and (= main_~a~0 1) (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:40,207 INFO L290 TraceCheckUtils]: 35: Hoare triple {2855#(and (= main_~a~0 1) (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} assume !false; {2855#(and (= main_~a~0 1) (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:40,207 INFO L272 TraceCheckUtils]: 36: Hoare triple {2855#(and (= main_~a~0 1) (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:40,207 INFO L290 TraceCheckUtils]: 37: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:40,207 INFO L290 TraceCheckUtils]: 38: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:40,207 INFO L290 TraceCheckUtils]: 39: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:40,208 INFO L284 TraceCheckUtils]: 40: Hoare quadruple {2744#true} {2855#(and (= main_~a~0 1) (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} #88#return; {2855#(and (= main_~a~0 1) (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:40,208 INFO L272 TraceCheckUtils]: 41: Hoare triple {2855#(and (= main_~a~0 1) (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:40,208 INFO L290 TraceCheckUtils]: 42: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:40,208 INFO L290 TraceCheckUtils]: 43: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:40,208 INFO L290 TraceCheckUtils]: 44: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:40,208 INFO L284 TraceCheckUtils]: 45: Hoare quadruple {2744#true} {2855#(and (= main_~a~0 1) (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} #90#return; {2855#(and (= main_~a~0 1) (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:40,208 INFO L272 TraceCheckUtils]: 46: Hoare triple {2855#(and (= main_~a~0 1) (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} call __VERIFIER_assert((if ~r~0 >= 0 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:40,209 INFO L290 TraceCheckUtils]: 47: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:40,209 INFO L290 TraceCheckUtils]: 48: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:40,209 INFO L290 TraceCheckUtils]: 49: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:40,209 INFO L284 TraceCheckUtils]: 50: Hoare quadruple {2744#true} {2855#(and (= main_~a~0 1) (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} #92#return; {2855#(and (= main_~a~0 1) (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:40,210 INFO L290 TraceCheckUtils]: 51: Hoare triple {2855#(and (= main_~a~0 1) (<= 0 main_~y~0) (= main_~x~0 main_~r~0) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} assume !(~r~0 >= 2 * ~b~0); {2907#(and (= main_~a~0 1) (= main_~x~0 main_~r~0) (< main_~r~0 (* main_~b~0 2)) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} is VALID [2022-04-07 13:01:40,211 INFO L290 TraceCheckUtils]: 52: Hoare triple {2907#(and (= main_~a~0 1) (= main_~x~0 main_~r~0) (< main_~r~0 (* main_~b~0 2)) (<= main_~y~0 main_~r~0) (<= main_~b~0 main_~y~0) (= main_~q~0 0) (<= main_~y~0 1))} ~r~0 := ~r~0 - ~b~0;~q~0 := ~q~0 + ~a~0; {2911#(and (= main_~q~0 1) (<= main_~x~0 (+ main_~y~0 main_~r~0)) (<= main_~y~0 1) (<= main_~y~0 main_~x~0) (< (* main_~r~0 2) main_~x~0))} is VALID [2022-04-07 13:01:40,211 INFO L290 TraceCheckUtils]: 53: Hoare triple {2911#(and (= main_~q~0 1) (<= main_~x~0 (+ main_~y~0 main_~r~0)) (<= main_~y~0 1) (<= main_~y~0 main_~x~0) (< (* main_~r~0 2) main_~x~0))} assume !false; {2911#(and (= main_~q~0 1) (<= main_~x~0 (+ main_~y~0 main_~r~0)) (<= main_~y~0 1) (<= main_~y~0 main_~x~0) (< (* main_~r~0 2) main_~x~0))} is VALID [2022-04-07 13:01:40,211 INFO L272 TraceCheckUtils]: 54: Hoare triple {2911#(and (= main_~q~0 1) (<= main_~x~0 (+ main_~y~0 main_~r~0)) (<= main_~y~0 1) (<= main_~y~0 main_~x~0) (< (* main_~r~0 2) main_~x~0))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:40,211 INFO L290 TraceCheckUtils]: 55: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:40,211 INFO L290 TraceCheckUtils]: 56: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:40,211 INFO L290 TraceCheckUtils]: 57: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:40,212 INFO L284 TraceCheckUtils]: 58: Hoare quadruple {2744#true} {2911#(and (= main_~q~0 1) (<= main_~x~0 (+ main_~y~0 main_~r~0)) (<= main_~y~0 1) (<= main_~y~0 main_~x~0) (< (* main_~r~0 2) main_~x~0))} #84#return; {2911#(and (= main_~q~0 1) (<= main_~x~0 (+ main_~y~0 main_~r~0)) (<= main_~y~0 1) (<= main_~y~0 main_~x~0) (< (* main_~r~0 2) main_~x~0))} is VALID [2022-04-07 13:01:40,212 INFO L272 TraceCheckUtils]: 59: Hoare triple {2911#(and (= main_~q~0 1) (<= main_~x~0 (+ main_~y~0 main_~r~0)) (<= main_~y~0 1) (<= main_~y~0 main_~x~0) (< (* main_~r~0 2) main_~x~0))} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {2933#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-07 13:01:40,213 INFO L290 TraceCheckUtils]: 60: Hoare triple {2933#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {2937#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-07 13:01:40,213 INFO L290 TraceCheckUtils]: 61: Hoare triple {2937#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {2745#false} is VALID [2022-04-07 13:01:40,213 INFO L290 TraceCheckUtils]: 62: Hoare triple {2745#false} assume !false; {2745#false} is VALID [2022-04-07 13:01:40,213 INFO L134 CoverageAnalysis]: Checked inductivity of 87 backedges. 15 proven. 6 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2022-04-07 13:01:40,213 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-07 13:01:41,199 INFO L290 TraceCheckUtils]: 62: Hoare triple {2745#false} assume !false; {2745#false} is VALID [2022-04-07 13:01:41,200 INFO L290 TraceCheckUtils]: 61: Hoare triple {2937#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {2745#false} is VALID [2022-04-07 13:01:41,200 INFO L290 TraceCheckUtils]: 60: Hoare triple {2933#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {2937#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-07 13:01:41,201 INFO L272 TraceCheckUtils]: 59: Hoare triple {2953#(= (+ (* main_~q~0 main_~y~0) main_~r~0) main_~x~0)} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {2933#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-07 13:01:41,202 INFO L284 TraceCheckUtils]: 58: Hoare quadruple {2744#true} {2953#(= (+ (* main_~q~0 main_~y~0) main_~r~0) main_~x~0)} #84#return; {2953#(= (+ (* main_~q~0 main_~y~0) main_~r~0) main_~x~0)} is VALID [2022-04-07 13:01:41,202 INFO L290 TraceCheckUtils]: 57: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:41,202 INFO L290 TraceCheckUtils]: 56: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:41,202 INFO L290 TraceCheckUtils]: 55: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:41,202 INFO L272 TraceCheckUtils]: 54: Hoare triple {2953#(= (+ (* main_~q~0 main_~y~0) main_~r~0) main_~x~0)} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:41,203 INFO L290 TraceCheckUtils]: 53: Hoare triple {2953#(= (+ (* main_~q~0 main_~y~0) main_~r~0) main_~x~0)} assume !false; {2953#(= (+ (* main_~q~0 main_~y~0) main_~r~0) main_~x~0)} is VALID [2022-04-07 13:01:41,287 INFO L290 TraceCheckUtils]: 52: Hoare triple {2975#(= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0))))} ~r~0 := ~r~0 - ~b~0;~q~0 := ~q~0 + ~a~0; {2953#(= (+ (* main_~q~0 main_~y~0) main_~r~0) main_~x~0)} is VALID [2022-04-07 13:01:41,288 INFO L290 TraceCheckUtils]: 51: Hoare triple {2979#(or (= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0)))) (<= (* main_~b~0 2) main_~r~0))} assume !(~r~0 >= 2 * ~b~0); {2975#(= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0))))} is VALID [2022-04-07 13:01:41,289 INFO L284 TraceCheckUtils]: 50: Hoare quadruple {2744#true} {2979#(or (= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0)))) (<= (* main_~b~0 2) main_~r~0))} #92#return; {2979#(or (= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0)))) (<= (* main_~b~0 2) main_~r~0))} is VALID [2022-04-07 13:01:41,289 INFO L290 TraceCheckUtils]: 49: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:41,289 INFO L290 TraceCheckUtils]: 48: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:41,289 INFO L290 TraceCheckUtils]: 47: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:41,289 INFO L272 TraceCheckUtils]: 46: Hoare triple {2979#(or (= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0)))) (<= (* main_~b~0 2) main_~r~0))} call __VERIFIER_assert((if ~r~0 >= 0 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:41,290 INFO L284 TraceCheckUtils]: 45: Hoare quadruple {2744#true} {2979#(or (= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0)))) (<= (* main_~b~0 2) main_~r~0))} #90#return; {2979#(or (= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0)))) (<= (* main_~b~0 2) main_~r~0))} is VALID [2022-04-07 13:01:41,290 INFO L290 TraceCheckUtils]: 44: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:41,290 INFO L290 TraceCheckUtils]: 43: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:41,290 INFO L290 TraceCheckUtils]: 42: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:41,290 INFO L272 TraceCheckUtils]: 41: Hoare triple {2979#(or (= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0)))) (<= (* main_~b~0 2) main_~r~0))} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:41,291 INFO L284 TraceCheckUtils]: 40: Hoare quadruple {2744#true} {2979#(or (= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0)))) (<= (* main_~b~0 2) main_~r~0))} #88#return; {2979#(or (= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0)))) (<= (* main_~b~0 2) main_~r~0))} is VALID [2022-04-07 13:01:41,291 INFO L290 TraceCheckUtils]: 39: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:41,291 INFO L290 TraceCheckUtils]: 38: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:41,291 INFO L290 TraceCheckUtils]: 37: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:41,291 INFO L272 TraceCheckUtils]: 36: Hoare triple {2979#(or (= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0)))) (<= (* main_~b~0 2) main_~r~0))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:41,292 INFO L290 TraceCheckUtils]: 35: Hoare triple {2979#(or (= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0)))) (<= (* main_~b~0 2) main_~r~0))} assume !false; {2979#(or (= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0)))) (<= (* main_~b~0 2) main_~r~0))} is VALID [2022-04-07 13:01:41,295 INFO L290 TraceCheckUtils]: 34: Hoare triple {3031#(or (and (or (<= main_~x~0 (+ (* main_~q~0 main_~y~0) main_~r~0)) (<= main_~y~0 (div main_~r~0 2))) (or (<= (+ (* main_~q~0 main_~y~0) main_~y~0 main_~r~0) (+ (div main_~r~0 2) main_~x~0 1)) (<= main_~y~0 (div main_~r~0 2)))) (not (<= main_~y~0 main_~r~0)))} assume !!(~r~0 >= ~y~0);~a~0 := 1;~b~0 := ~y~0; {2979#(or (= main_~x~0 (+ main_~r~0 (* (- 1) main_~b~0) (* main_~y~0 (+ main_~a~0 main_~q~0)))) (<= (* main_~b~0 2) main_~r~0))} is VALID [2022-04-07 13:01:41,296 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {2744#true} {3031#(or (and (or (<= main_~x~0 (+ (* main_~q~0 main_~y~0) main_~r~0)) (<= main_~y~0 (div main_~r~0 2))) (or (<= (+ (* main_~q~0 main_~y~0) main_~y~0 main_~r~0) (+ (div main_~r~0 2) main_~x~0 1)) (<= main_~y~0 (div main_~r~0 2)))) (not (<= main_~y~0 main_~r~0)))} #86#return; {3031#(or (and (or (<= main_~x~0 (+ (* main_~q~0 main_~y~0) main_~r~0)) (<= main_~y~0 (div main_~r~0 2))) (or (<= (+ (* main_~q~0 main_~y~0) main_~y~0 main_~r~0) (+ (div main_~r~0 2) main_~x~0 1)) (<= main_~y~0 (div main_~r~0 2)))) (not (<= main_~y~0 main_~r~0)))} is VALID [2022-04-07 13:01:41,296 INFO L290 TraceCheckUtils]: 32: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:41,296 INFO L290 TraceCheckUtils]: 31: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:41,296 INFO L290 TraceCheckUtils]: 30: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:41,296 INFO L272 TraceCheckUtils]: 29: Hoare triple {3031#(or (and (or (<= main_~x~0 (+ (* main_~q~0 main_~y~0) main_~r~0)) (<= main_~y~0 (div main_~r~0 2))) (or (<= (+ (* main_~q~0 main_~y~0) main_~y~0 main_~r~0) (+ (div main_~r~0 2) main_~x~0 1)) (<= main_~y~0 (div main_~r~0 2)))) (not (<= main_~y~0 main_~r~0)))} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:41,296 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {2744#true} {3031#(or (and (or (<= main_~x~0 (+ (* main_~q~0 main_~y~0) main_~r~0)) (<= main_~y~0 (div main_~r~0 2))) (or (<= (+ (* main_~q~0 main_~y~0) main_~y~0 main_~r~0) (+ (div main_~r~0 2) main_~x~0 1)) (<= main_~y~0 (div main_~r~0 2)))) (not (<= main_~y~0 main_~r~0)))} #84#return; {3031#(or (and (or (<= main_~x~0 (+ (* main_~q~0 main_~y~0) main_~r~0)) (<= main_~y~0 (div main_~r~0 2))) (or (<= (+ (* main_~q~0 main_~y~0) main_~y~0 main_~r~0) (+ (div main_~r~0 2) main_~x~0 1)) (<= main_~y~0 (div main_~r~0 2)))) (not (<= main_~y~0 main_~r~0)))} is VALID [2022-04-07 13:01:41,297 INFO L290 TraceCheckUtils]: 27: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:41,297 INFO L290 TraceCheckUtils]: 26: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:41,297 INFO L290 TraceCheckUtils]: 25: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:41,297 INFO L272 TraceCheckUtils]: 24: Hoare triple {3031#(or (and (or (<= main_~x~0 (+ (* main_~q~0 main_~y~0) main_~r~0)) (<= main_~y~0 (div main_~r~0 2))) (or (<= (+ (* main_~q~0 main_~y~0) main_~y~0 main_~r~0) (+ (div main_~r~0 2) main_~x~0 1)) (<= main_~y~0 (div main_~r~0 2)))) (not (<= main_~y~0 main_~r~0)))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:41,297 INFO L290 TraceCheckUtils]: 23: Hoare triple {3031#(or (and (or (<= main_~x~0 (+ (* main_~q~0 main_~y~0) main_~r~0)) (<= main_~y~0 (div main_~r~0 2))) (or (<= (+ (* main_~q~0 main_~y~0) main_~y~0 main_~r~0) (+ (div main_~r~0 2) main_~x~0 1)) (<= main_~y~0 (div main_~r~0 2)))) (not (<= main_~y~0 main_~r~0)))} assume !false; {3031#(or (and (or (<= main_~x~0 (+ (* main_~q~0 main_~y~0) main_~r~0)) (<= main_~y~0 (div main_~r~0 2))) (or (<= (+ (* main_~q~0 main_~y~0) main_~y~0 main_~r~0) (+ (div main_~r~0 2) main_~x~0 1)) (<= main_~y~0 (div main_~r~0 2)))) (not (<= main_~y~0 main_~r~0)))} is VALID [2022-04-07 13:01:41,298 INFO L290 TraceCheckUtils]: 22: Hoare triple {3068#(<= main_~y~0 (+ 2 (div (+ (- 2) main_~y~0) 2)))} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {3031#(or (and (or (<= main_~x~0 (+ (* main_~q~0 main_~y~0) main_~r~0)) (<= main_~y~0 (div main_~r~0 2))) (or (<= (+ (* main_~q~0 main_~y~0) main_~y~0 main_~r~0) (+ (div main_~r~0 2) main_~x~0 1)) (<= main_~y~0 (div main_~r~0 2)))) (not (<= main_~y~0 main_~r~0)))} is VALID [2022-04-07 13:01:41,298 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {2744#true} {3068#(<= main_~y~0 (+ 2 (div (+ (- 2) main_~y~0) 2)))} #82#return; {3068#(<= main_~y~0 (+ 2 (div (+ (- 2) main_~y~0) 2)))} is VALID [2022-04-07 13:01:41,298 INFO L290 TraceCheckUtils]: 20: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:41,298 INFO L290 TraceCheckUtils]: 19: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:41,298 INFO L290 TraceCheckUtils]: 18: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:41,299 INFO L272 TraceCheckUtils]: 17: Hoare triple {3068#(<= main_~y~0 (+ 2 (div (+ (- 2) main_~y~0) 2)))} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:41,299 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {2792#(not (= |assume_abort_if_not_#in~cond| 0))} {2744#true} #80#return; {3068#(<= main_~y~0 (+ 2 (div (+ (- 2) main_~y~0) 2)))} is VALID [2022-04-07 13:01:41,299 INFO L290 TraceCheckUtils]: 15: Hoare triple {2792#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {2792#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:41,300 INFO L290 TraceCheckUtils]: 14: Hoare triple {3096#(or (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond 0))} assume !(0 == ~cond); {2792#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-07 13:01:41,300 INFO L290 TraceCheckUtils]: 13: Hoare triple {2744#true} ~cond := #in~cond; {3096#(or (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond 0))} is VALID [2022-04-07 13:01:41,300 INFO L272 TraceCheckUtils]: 12: Hoare triple {2744#true} call assume_abort_if_not((if ~y~0 >= 0 && ~y~0 <= 1 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:41,300 INFO L290 TraceCheckUtils]: 11: Hoare triple {2744#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {2744#true} is VALID [2022-04-07 13:01:41,300 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2744#true} {2744#true} #78#return; {2744#true} is VALID [2022-04-07 13:01:41,300 INFO L290 TraceCheckUtils]: 9: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:41,300 INFO L290 TraceCheckUtils]: 8: Hoare triple {2744#true} assume !(0 == ~cond); {2744#true} is VALID [2022-04-07 13:01:41,300 INFO L290 TraceCheckUtils]: 7: Hoare triple {2744#true} ~cond := #in~cond; {2744#true} is VALID [2022-04-07 13:01:41,300 INFO L272 TraceCheckUtils]: 6: Hoare triple {2744#true} call assume_abort_if_not((if ~x~0 >= 0 && ~x~0 <= 1 then 1 else 0)); {2744#true} is VALID [2022-04-07 13:01:41,300 INFO L290 TraceCheckUtils]: 5: Hoare triple {2744#true} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4; {2744#true} is VALID [2022-04-07 13:01:41,300 INFO L272 TraceCheckUtils]: 4: Hoare triple {2744#true} call #t~ret6 := main(); {2744#true} is VALID [2022-04-07 13:01:41,300 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2744#true} {2744#true} #98#return; {2744#true} is VALID [2022-04-07 13:01:41,300 INFO L290 TraceCheckUtils]: 2: Hoare triple {2744#true} assume true; {2744#true} is VALID [2022-04-07 13:01:41,301 INFO L290 TraceCheckUtils]: 1: Hoare triple {2744#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(14, 2);call #Ultimate.allocInit(12, 3); {2744#true} is VALID [2022-04-07 13:01:41,301 INFO L272 TraceCheckUtils]: 0: Hoare triple {2744#true} call ULTIMATE.init(); {2744#true} is VALID [2022-04-07 13:01:41,301 INFO L134 CoverageAnalysis]: Checked inductivity of 87 backedges. 15 proven. 6 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2022-04-07 13:01:41,301 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-07 13:01:41,301 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1397880018] [2022-04-07 13:01:41,301 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-07 13:01:41,301 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [894913361] [2022-04-07 13:01:41,301 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [894913361] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-07 13:01:41,301 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-07 13:01:41,301 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 17 [2022-04-07 13:01:41,301 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1087883054] [2022-04-07 13:01:41,301 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-07 13:01:41,302 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 9 states have call predecessors, (18), 9 states have call successors, (18) Word has length 63 [2022-04-07 13:01:41,302 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-07 13:01:41,302 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 9 states have call predecessors, (18), 9 states have call successors, (18) [2022-04-07 13:01:41,361 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 70 edges. 70 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 13:01:41,361 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-04-07 13:01:41,362 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-07 13:01:41,362 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-04-07 13:01:41,362 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=215, Unknown=0, NotChecked=0, Total=272 [2022-04-07 13:01:41,362 INFO L87 Difference]: Start difference. First operand 55 states and 62 transitions. Second operand has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 9 states have call predecessors, (18), 9 states have call successors, (18) [2022-04-07 13:01:42,166 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:42,167 INFO L93 Difference]: Finished difference Result 75 states and 84 transitions. [2022-04-07 13:01:42,167 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-07 13:01:42,167 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 9 states have call predecessors, (18), 9 states have call successors, (18) Word has length 63 [2022-04-07 13:01:42,167 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-07 13:01:42,167 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 9 states have call predecessors, (18), 9 states have call successors, (18) [2022-04-07 13:01:42,168 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 66 transitions. [2022-04-07 13:01:42,168 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 9 states have call predecessors, (18), 9 states have call successors, (18) [2022-04-07 13:01:42,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 66 transitions. [2022-04-07 13:01:42,170 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 11 states and 66 transitions. [2022-04-07 13:01:42,223 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 66 edges. 66 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-07 13:01:42,223 INFO L225 Difference]: With dead ends: 75 [2022-04-07 13:01:42,223 INFO L226 Difference]: Without dead ends: 0 [2022-04-07 13:01:42,223 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 109 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 76 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=97, Invalid=365, Unknown=0, NotChecked=0, Total=462 [2022-04-07 13:01:42,224 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 20 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 253 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 282 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 253 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-07 13:01:42,224 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [20 Valid, 139 Invalid, 282 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 253 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-07 13:01:42,224 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-07 13:01:42,224 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-07 13:01:42,224 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-07 13:01:42,224 INFO L82 GeneralOperation]: Start isEquivalent. First operand 0 states. Second operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-07 13:01:42,225 INFO L74 IsIncluded]: Start isIncluded. First operand 0 states. Second operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-07 13:01:42,225 INFO L87 Difference]: Start difference. First operand 0 states. Second operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-07 13:01:42,225 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:42,225 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-07 13:01:42,225 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-07 13:01:42,225 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:42,225 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:42,225 INFO L74 IsIncluded]: Start isIncluded. First operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand 0 states. [2022-04-07 13:01:42,225 INFO L87 Difference]: Start difference. First operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand 0 states. [2022-04-07 13:01:42,225 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-07 13:01:42,225 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-07 13:01:42,225 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-07 13:01:42,225 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:42,225 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-07 13:01:42,225 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-07 13:01:42,225 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-07 13:01:42,225 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-07 13:01:42,226 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-07 13:01:42,226 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 63 [2022-04-07 13:01:42,226 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-07 13:01:42,226 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-07 13:01:42,226 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.8823529411764706) internal successors, (32), 14 states have internal predecessors, (32), 9 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 9 states have call predecessors, (18), 9 states have call successors, (18) [2022-04-07 13:01:42,226 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-07 13:01:42,226 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-07 13:01:42,228 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-07 13:01:42,243 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-07 13:01:42,428 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-07 13:01:42,430 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-04-07 13:01:42,977 INFO L882 garLoopResultBuilder]: For program point reach_errorEXIT(line 8) no Hoare annotation was computed. [2022-04-07 13:01:42,978 INFO L882 garLoopResultBuilder]: For program point reach_errorENTRY(line 8) no Hoare annotation was computed. [2022-04-07 13:01:42,978 INFO L882 garLoopResultBuilder]: For program point reach_errorFINAL(line 8) no Hoare annotation was computed. [2022-04-07 13:01:42,978 INFO L885 garLoopResultBuilder]: At program point assume_abort_if_notENTRY(lines 11 13) the Hoare annotation is: true [2022-04-07 13:01:42,978 INFO L882 garLoopResultBuilder]: For program point L12(line 12) no Hoare annotation was computed. [2022-04-07 13:01:42,978 INFO L882 garLoopResultBuilder]: For program point L12-2(lines 11 13) no Hoare annotation was computed. [2022-04-07 13:01:42,978 INFO L882 garLoopResultBuilder]: For program point assume_abort_if_notEXIT(lines 11 13) no Hoare annotation was computed. [2022-04-07 13:01:42,978 INFO L882 garLoopResultBuilder]: For program point L64(line 64) no Hoare annotation was computed. [2022-04-07 13:01:42,978 INFO L882 garLoopResultBuilder]: For program point L31(line 31) no Hoare annotation was computed. [2022-04-07 13:01:42,978 INFO L878 garLoopResultBuilder]: At program point L29(line 29) the Hoare annotation is: (and (<= 0 main_~x~0) (<= main_~x~0 1)) [2022-04-07 13:01:42,978 INFO L878 garLoopResultBuilder]: At program point L29-1(line 29) the Hoare annotation is: (and (<= 0 main_~y~0) (<= 0 main_~x~0) (<= main_~x~0 1) (<= main_~y~0 1)) [2022-04-07 13:01:42,978 INFO L885 garLoopResultBuilder]: At program point L27(line 27) the Hoare annotation is: true [2022-04-07 13:01:42,978 INFO L882 garLoopResultBuilder]: For program point L27-1(line 27) no Hoare annotation was computed. [2022-04-07 13:01:42,978 INFO L882 garLoopResultBuilder]: For program point mainEXIT(lines 22 66) no Hoare annotation was computed. [2022-04-07 13:01:42,978 INFO L882 garLoopResultBuilder]: For program point L50(lines 47 59) no Hoare annotation was computed. [2022-04-07 13:01:42,978 INFO L878 garLoopResultBuilder]: At program point L48(line 48) the Hoare annotation is: (and (= main_~x~0 main_~r~0) (<= main_~x~0 1) (<= 1 main_~r~0) (= main_~b~0 main_~y~0) (= (+ (* main_~q~0 main_~y~0) main_~r~0 (* main_~a~0 main_~y~0)) (+ main_~b~0 main_~x~0)) (= main_~q~0 0) (<= 1 main_~y~0) (<= main_~y~0 1)) [2022-04-07 13:01:42,978 INFO L878 garLoopResultBuilder]: At program point L48-1(line 48) the Hoare annotation is: (and (= main_~x~0 main_~r~0) (<= main_~x~0 1) (<= 1 main_~r~0) (= main_~b~0 main_~y~0) (= (+ (* main_~q~0 main_~y~0) main_~r~0 (* main_~a~0 main_~y~0)) (+ main_~b~0 main_~x~0)) (= main_~q~0 0) (<= 1 main_~y~0) (<= main_~y~0 1)) [2022-04-07 13:01:42,979 INFO L882 garLoopResultBuilder]: For program point mainFINAL(lines 22 66) no Hoare annotation was computed. [2022-04-07 13:01:42,979 INFO L882 garLoopResultBuilder]: For program point L40(lines 38 62) no Hoare annotation was computed. [2022-04-07 13:01:42,979 INFO L878 garLoopResultBuilder]: At program point L38-2(lines 38 62) the Hoare annotation is: (let ((.cse0 (= (+ (* main_~q~0 main_~y~0) main_~r~0 (* main_~a~0 main_~y~0)) (+ main_~b~0 main_~x~0))) (.cse1 (<= main_~y~0 1))) (or (and (= main_~x~0 main_~r~0) (= main_~b~0 0) (<= 0 main_~x~0) (<= main_~x~0 1) .cse0 (= main_~q~0 0) (<= 1 main_~y~0) .cse1) (and (= main_~b~0 main_~y~0) .cse0 (= main_~q~0 1) (<= main_~x~0 (+ main_~y~0 main_~r~0)) .cse1 (<= main_~y~0 main_~x~0) (< (* main_~r~0 2) main_~x~0)))) [2022-04-07 13:01:42,979 INFO L878 garLoopResultBuilder]: At program point L38-3(lines 38 62) the Hoare annotation is: (let ((.cse0 (<= main_~y~0 1))) (or (and (= main_~x~0 main_~r~0) (= main_~q~0 0) (<= 1 main_~y~0) .cse0) (and (= (+ (* main_~q~0 main_~y~0) main_~r~0 (* main_~a~0 main_~y~0)) (+ main_~b~0 main_~x~0)) (<= 1 main_~b~0) (= main_~q~0 1) (<= main_~x~0 (+ main_~y~0 main_~r~0)) .cse0 (<= main_~y~0 main_~x~0) (< (* main_~r~0 2) main_~x~0)))) [2022-04-07 13:01:42,979 INFO L885 garLoopResultBuilder]: At program point mainENTRY(lines 22 66) the Hoare annotation is: true [2022-04-07 13:01:42,979 INFO L878 garLoopResultBuilder]: At program point L55(line 55) the Hoare annotation is: false [2022-04-07 13:01:42,979 INFO L882 garLoopResultBuilder]: For program point L55-1(line 55) no Hoare annotation was computed. [2022-04-07 13:01:42,979 INFO L878 garLoopResultBuilder]: At program point L49(line 49) the Hoare annotation is: (and (= main_~a~0 1) (<= main_~x~0 1) (<= 1 main_~r~0) (= main_~b~0 main_~y~0) (= (+ (* main_~q~0 main_~y~0) main_~r~0 (* main_~a~0 main_~y~0)) (+ main_~b~0 main_~x~0)) (= main_~q~0 0) (<= 1 main_~y~0) (<= main_~y~0 1)) [2022-04-07 13:01:42,979 INFO L878 garLoopResultBuilder]: At program point L47-2(lines 47 59) the Hoare annotation is: (and (= main_~x~0 main_~r~0) (<= main_~x~0 1) (<= 1 main_~r~0) (= main_~b~0 main_~y~0) (= (+ (* main_~q~0 main_~y~0) main_~r~0 (* main_~a~0 main_~y~0)) (+ main_~b~0 main_~x~0)) (= main_~q~0 0) (<= 1 main_~y~0) (<= main_~y~0 1)) [2022-04-07 13:01:42,979 INFO L882 garLoopResultBuilder]: For program point L47-3(lines 47 59) no Hoare annotation was computed. [2022-04-07 13:01:42,980 INFO L878 garLoopResultBuilder]: At program point L39(line 39) the Hoare annotation is: (let ((.cse0 (= (+ (* main_~q~0 main_~y~0) main_~r~0 (* main_~a~0 main_~y~0)) (+ main_~b~0 main_~x~0))) (.cse1 (<= main_~y~0 1))) (or (and (= main_~x~0 main_~r~0) (= main_~b~0 0) (<= 0 main_~x~0) (<= main_~x~0 1) .cse0 (= main_~q~0 0) (<= 1 main_~y~0) .cse1) (and (= main_~b~0 main_~y~0) .cse0 (= main_~q~0 1) (<= main_~x~0 (+ main_~y~0 main_~r~0)) .cse1 (<= main_~y~0 main_~x~0) (< (* main_~r~0 2) main_~x~0)))) [2022-04-07 13:01:42,980 INFO L878 garLoopResultBuilder]: At program point L39-1(line 39) the Hoare annotation is: (let ((.cse0 (= (+ (* main_~q~0 main_~y~0) main_~r~0 (* main_~a~0 main_~y~0)) (+ main_~b~0 main_~x~0))) (.cse1 (<= main_~y~0 1))) (or (and (= main_~x~0 main_~r~0) (<= 0 main_~x~0) (<= main_~x~0 1) .cse0 (= main_~q~0 0) (<= 1 main_~y~0) .cse1) (and .cse0 (<= 1 main_~b~0) (= main_~q~0 1) (<= main_~x~0 (+ main_~y~0 main_~r~0)) .cse1 (<= main_~y~0 main_~x~0) (< (* main_~r~0 2) main_~x~0)))) [2022-04-07 13:01:42,980 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.initFINAL(line -1) no Hoare annotation was computed. [2022-04-07 13:01:42,980 INFO L878 garLoopResultBuilder]: At program point ULTIMATE.initENTRY(line -1) the Hoare annotation is: (and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|)) [2022-04-07 13:01:42,980 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.initEXIT(line -1) no Hoare annotation was computed. [2022-04-07 13:01:42,980 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.startEXIT(line -1) no Hoare annotation was computed. [2022-04-07 13:01:42,980 INFO L885 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-04-07 13:01:42,980 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-04-07 13:01:42,980 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.startFINAL(line -1) no Hoare annotation was computed. [2022-04-07 13:01:42,980 INFO L882 garLoopResultBuilder]: For program point L16(lines 16 17) no Hoare annotation was computed. [2022-04-07 13:01:42,980 INFO L882 garLoopResultBuilder]: For program point L15(lines 15 18) no Hoare annotation was computed. [2022-04-07 13:01:42,980 INFO L885 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 14 20) the Hoare annotation is: true [2022-04-07 13:01:42,980 INFO L882 garLoopResultBuilder]: For program point L15-2(lines 14 20) no Hoare annotation was computed. [2022-04-07 13:01:42,980 INFO L882 garLoopResultBuilder]: For program point __VERIFIER_assertEXIT(lines 14 20) no Hoare annotation was computed. [2022-04-07 13:01:42,981 INFO L882 garLoopResultBuilder]: For program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 17) no Hoare annotation was computed. [2022-04-07 13:01:42,986 INFO L719 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1, 1, 1] [2022-04-07 13:01:42,987 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-04-07 13:01:42,989 WARN L170 areAnnotationChecker]: reach_errorENTRY has no Hoare annotation [2022-04-07 13:01:42,989 WARN L170 areAnnotationChecker]: ULTIMATE.initFINAL has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L12 has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L15 has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: reach_errorFINAL has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: ULTIMATE.initFINAL has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: ULTIMATE.startFINAL has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L12 has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L12 has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L27-1 has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L15 has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L15 has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: ULTIMATE.initEXIT has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: ULTIMATE.startFINAL has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L12-2 has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L27-1 has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L16 has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L16 has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L15-2 has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: assume_abort_if_notEXIT has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: assume_abort_if_notEXIT has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: assume_abort_if_notEXIT has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L31 has no Hoare annotation [2022-04-07 13:01:42,990 WARN L170 areAnnotationChecker]: L31 has no Hoare annotation [2022-04-07 13:01:42,991 WARN L170 areAnnotationChecker]: L40 has no Hoare annotation [2022-04-07 13:01:42,991 WARN L170 areAnnotationChecker]: L40 has no Hoare annotation [2022-04-07 13:01:42,991 WARN L170 areAnnotationChecker]: L40 has no Hoare annotation [2022-04-07 13:01:42,991 WARN L170 areAnnotationChecker]: L50 has no Hoare annotation [2022-04-07 13:01:42,991 WARN L170 areAnnotationChecker]: L50 has no Hoare annotation [2022-04-07 13:01:42,991 WARN L170 areAnnotationChecker]: L50 has no Hoare annotation [2022-04-07 13:01:42,991 WARN L170 areAnnotationChecker]: L55-1 has no Hoare annotation [2022-04-07 13:01:42,991 WARN L170 areAnnotationChecker]: L64 has no Hoare annotation [2022-04-07 13:01:43,004 WARN L170 areAnnotationChecker]: L64 has no Hoare annotation [2022-04-07 13:01:43,004 WARN L170 areAnnotationChecker]: L47-3 has no Hoare annotation [2022-04-07 13:01:43,004 WARN L170 areAnnotationChecker]: L47-3 has no Hoare annotation [2022-04-07 13:01:43,005 WARN L170 areAnnotationChecker]: L47-3 has no Hoare annotation [2022-04-07 13:01:43,005 WARN L170 areAnnotationChecker]: L55-1 has no Hoare annotation [2022-04-07 13:01:43,005 WARN L170 areAnnotationChecker]: mainFINAL has no Hoare annotation [2022-04-07 13:01:43,005 WARN L170 areAnnotationChecker]: mainEXIT has no Hoare annotation [2022-04-07 13:01:43,005 INFO L163 areAnnotationChecker]: CFG has 17 edges. 17 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. 0 times interpolants missing. [2022-04-07 13:01:43,012 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 07.04 01:01:43 BoogieIcfgContainer [2022-04-07 13:01:43,012 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-07 13:01:43,013 INFO L158 Benchmark]: Toolchain (without parser) took 11329.56ms. Allocated memory was 173.0MB in the beginning and 267.4MB in the end (delta: 94.4MB). Free memory was 123.3MB in the beginning and 182.9MB in the end (delta: -59.7MB). Peak memory consumption was 35.2MB. Max. memory is 8.0GB. [2022-04-07 13:01:43,013 INFO L158 Benchmark]: CDTParser took 0.08ms. Allocated memory is still 173.0MB. Free memory is still 139.5MB. There was no memory consumed. Max. memory is 8.0GB. [2022-04-07 13:01:43,013 INFO L158 Benchmark]: CACSL2BoogieTranslator took 184.02ms. Allocated memory is still 173.0MB. Free memory was 122.9MB in the beginning and 148.1MB in the end (delta: -25.2MB). Peak memory consumption was 11.8MB. Max. memory is 8.0GB. [2022-04-07 13:01:43,013 INFO L158 Benchmark]: Boogie Preprocessor took 23.89ms. Allocated memory is still 173.0MB. Free memory was 148.1MB in the beginning and 146.6MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-07 13:01:43,013 INFO L158 Benchmark]: RCFGBuilder took 269.75ms. Allocated memory is still 173.0MB. Free memory was 146.5MB in the beginning and 134.5MB in the end (delta: 12.0MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2022-04-07 13:01:43,014 INFO L158 Benchmark]: TraceAbstraction took 10847.21ms. Allocated memory was 173.0MB in the beginning and 267.4MB in the end (delta: 94.4MB). Free memory was 133.9MB in the beginning and 182.9MB in the end (delta: -49.0MB). Peak memory consumption was 46.4MB. Max. memory is 8.0GB. [2022-04-07 13:01:43,014 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.08ms. Allocated memory is still 173.0MB. Free memory is still 139.5MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 184.02ms. Allocated memory is still 173.0MB. Free memory was 122.9MB in the beginning and 148.1MB in the end (delta: -25.2MB). Peak memory consumption was 11.8MB. Max. memory is 8.0GB. * Boogie Preprocessor took 23.89ms. Allocated memory is still 173.0MB. Free memory was 148.1MB in the beginning and 146.6MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 269.75ms. Allocated memory is still 173.0MB. Free memory was 146.5MB in the beginning and 134.5MB in the end (delta: 12.0MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * TraceAbstraction took 10847.21ms. Allocated memory was 173.0MB in the beginning and 267.4MB in the end (delta: 94.4MB). Free memory was 133.9MB in the beginning and 182.9MB in the end (delta: -49.0MB). Peak memory consumption was 46.4MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 17]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 42 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 10.8s, OverallIterations: 7, TraceHistogramMax: 7, PathProgramHistogramMax: 1, EmptinessCheckTime: 0.0s, AutomataDifference: 3.3s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.5s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 204 SdHoareTripleChecker+Valid, 0.9s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 161 mSDsluCounter, 1078 SdHoareTripleChecker+Invalid, 0.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 830 mSDsCounter, 95 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 990 IncrementalHoareTripleChecker+Invalid, 1085 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 95 mSolverCounterUnsat, 248 mSDtfsCounter, 990 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 413 GetRequests, 341 SyntacticMatches, 1 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 126 ImplicationChecksByTransitivity, 0.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=74occurred in iteration=5, InterpolantAutomatonStates: 57, 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, 13 StatesRemovedByMinimization, 4 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 18 LocationsWithAnnotation, 58 PreInvPairs, 72 NumberOfFragments, 426 HoareAnnotationTreeSize, 58 FomulaSimplifications, 18 FormulaSimplificationTreeSizeReduction, 0.1s HoareSimplificationTime, 18 FomulaSimplificationsInter, 348 FormulaSimplificationTreeSizeReductionInter, 0.4s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.1s SatisfiabilityAnalysisTime, 4.5s InterpolantComputationTime, 298 NumberOfCodeBlocks, 298 NumberOfCodeBlocksAsserted, 7 NumberOfCheckSat, 408 ConstructedInterpolants, 0 QuantifiedInterpolants, 1398 SizeOfPredicates, 26 NumberOfNonLiveVariables, 745 ConjunctsInSsa, 94 ConjunctsInUnsatCore, 9 InterpolantComputations, 5 PerfectInterpolantSequences, 382/400 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 47]: Loop Invariant Derived loop invariant: ((((((x == r && x <= 1) && 1 <= r) && b == y) && q * y + r + a * y == b + x) && q == 0) && 1 <= y) && y <= 1 - InvariantResult [Line: 38]: Loop Invariant Derived loop invariant: (((((((x == r && b == 0) && 0 <= x) && x <= 1) && q * y + r + a * y == b + x) && q == 0) && 1 <= y) && y <= 1) || ((((((b == y && q * y + r + a * y == b + x) && q == 1) && x <= y + r) && y <= 1) && y <= x) && r * 2 < x) RESULT: Ultimate proved your program to be correct! [2022-04-07 13:01:43,031 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...