/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/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/prod4br-ll_unwindbound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-08 07:24:58,925 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-08 07:24:58,936 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-08 07:24:58,985 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-08 07:24:58,986 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-08 07:24:58,987 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-08 07:24:58,989 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-08 07:24:58,994 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-08 07:24:58,996 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-08 07:24:59,000 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-08 07:24:59,000 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-08 07:24:59,002 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-08 07:24:59,002 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-08 07:24:59,004 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-08 07:24:59,005 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-08 07:24:59,007 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-08 07:24:59,008 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-08 07:24:59,009 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-08 07:24:59,011 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-08 07:24:59,016 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-08 07:24:59,017 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-08 07:24:59,018 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-08 07:24:59,019 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-08 07:24:59,020 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-08 07:24:59,021 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-08 07:24:59,027 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-08 07:24:59,027 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-08 07:24:59,027 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-08 07:24:59,028 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-08 07:24:59,028 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-08 07:24:59,029 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-08 07:24:59,030 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-08 07:24:59,031 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-08 07:24:59,032 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-08 07:24:59,032 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-08 07:24:59,033 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-08 07:24:59,033 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-08 07:24:59,034 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-08 07:24:59,034 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-08 07:24:59,034 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-08 07:24:59,034 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-08 07:24:59,036 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-08 07:24:59,037 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-04-08 07:24:59,046 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-08 07:24:59,046 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-08 07:24:59,047 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-08 07:24:59,047 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-08 07:24:59,047 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-08 07:24:59,048 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-08 07:24:59,048 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-08 07:24:59,048 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-08 07:24:59,048 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-08 07:24:59,049 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-08 07:24:59,049 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-08 07:24:59,049 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-08 07:24:59,049 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-08 07:24:59,049 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-08 07:24:59,050 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-08 07:24:59,050 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-08 07:24:59,050 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-08 07:24:59,050 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-08 07:24:59,050 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 07:24:59,050 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-08 07:24:59,050 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-08 07:24:59,051 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-08 07:24:59,051 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-08 07:24:59,051 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-08 07:24:59,051 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-08 07:24:59,051 INFO L138 SettingsManager]: * Use separate solver for trace checks=false 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-08 07:24:59,291 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-08 07:24:59,315 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-08 07:24:59,317 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-08 07:24:59,318 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-08 07:24:59,318 INFO L275 PluginConnector]: CDTParser initialized [2022-04-08 07:24:59,319 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/prod4br-ll_unwindbound20.c [2022-04-08 07:24:59,368 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/38e181d3d/f343d324963e4aacb988f41a645d8988/FLAG351d6bf4b [2022-04-08 07:24:59,745 INFO L306 CDTParser]: Found 1 translation units. [2022-04-08 07:24:59,745 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/prod4br-ll_unwindbound20.c [2022-04-08 07:24:59,750 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/38e181d3d/f343d324963e4aacb988f41a645d8988/FLAG351d6bf4b [2022-04-08 07:25:00,160 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/38e181d3d/f343d324963e4aacb988f41a645d8988 [2022-04-08 07:25:00,162 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-08 07:25:00,163 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-08 07:25:00,166 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-08 07:25:00,166 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-08 07:25:00,170 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-08 07:25:00,171 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 07:25:00" (1/1) ... [2022-04-08 07:25:00,172 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7c29f968 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 07:25:00, skipping insertion in model container [2022-04-08 07:25:00,172 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 07:25:00" (1/1) ... [2022-04-08 07:25:00,178 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-08 07:25:00,190 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-08 07:25:00,332 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/prod4br-ll_unwindbound20.c[524,537] [2022-04-08 07:25:00,362 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 07:25:00,370 INFO L203 MainTranslator]: Completed pre-run [2022-04-08 07:25:00,380 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/prod4br-ll_unwindbound20.c[524,537] [2022-04-08 07:25:00,390 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 07:25:00,400 INFO L208 MainTranslator]: Completed translation [2022-04-08 07:25:00,400 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 07:25:00 WrapperNode [2022-04-08 07:25:00,401 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-08 07:25:00,401 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-08 07:25:00,402 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-08 07:25:00,402 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-08 07:25:00,411 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 07:25:00" (1/1) ... [2022-04-08 07:25:00,411 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 07:25:00" (1/1) ... [2022-04-08 07:25:00,431 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 07:25:00" (1/1) ... [2022-04-08 07:25:00,431 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 07:25:00" (1/1) ... [2022-04-08 07:25:00,438 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 07:25:00" (1/1) ... [2022-04-08 07:25:00,442 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 07:25:00" (1/1) ... [2022-04-08 07:25:00,443 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 07:25:00" (1/1) ... [2022-04-08 07:25:00,444 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-08 07:25:00,445 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-08 07:25:00,445 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-08 07:25:00,445 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-08 07:25:00,446 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 07:25:00" (1/1) ... [2022-04-08 07:25:00,455 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 07:25:00,470 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 07:25:00,478 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-08 07:25:00,480 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-08 07:25:00,508 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-08 07:25:00,508 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-08 07:25:00,508 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-08 07:25:00,508 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-08 07:25:00,509 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-08 07:25:00,509 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-08 07:25:00,509 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-08 07:25:00,509 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-08 07:25:00,509 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-08 07:25:00,509 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-08 07:25:00,509 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-08 07:25:00,509 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-08 07:25:00,509 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-08 07:25:00,510 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-08 07:25:00,510 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-08 07:25:00,510 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-08 07:25:00,510 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-08 07:25:00,510 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-08 07:25:00,510 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-08 07:25:00,510 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-08 07:25:00,559 INFO L234 CfgBuilder]: Building ICFG [2022-04-08 07:25:00,561 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-08 07:25:00,779 INFO L275 CfgBuilder]: Performing block encoding [2022-04-08 07:25:00,784 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-08 07:25:00,785 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-08 07:25:00,786 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 07:25:00 BoogieIcfgContainer [2022-04-08 07:25:00,786 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-08 07:25:00,787 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-08 07:25:00,787 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-08 07:25:00,790 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-08 07:25:00,790 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.04 07:25:00" (1/3) ... [2022-04-08 07:25:00,791 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@52fb8133 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 07:25:00, skipping insertion in model container [2022-04-08 07:25:00,791 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 07:25:00" (2/3) ... [2022-04-08 07:25:00,791 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@52fb8133 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 07:25:00, skipping insertion in model container [2022-04-08 07:25:00,791 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 07:25:00" (3/3) ... [2022-04-08 07:25:00,792 INFO L111 eAbstractionObserver]: Analyzing ICFG prod4br-ll_unwindbound20.c [2022-04-08 07:25:00,796 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-08 07:25:00,796 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-08 07:25:00,846 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-08 07:25:00,861 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, 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-08 07:25:00,861 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-08 07:25:00,884 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 20 states have (on average 1.45) internal successors, (29), 21 states have internal predecessors, (29), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-08 07:25:00,890 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-08 07:25:00,890 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 07:25:00,891 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 07:25:00,892 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 07:25:00,900 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 07:25:00,900 INFO L85 PathProgramCache]: Analyzing trace with hash 1717894843, now seen corresponding path program 1 times [2022-04-08 07:25:00,907 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 07:25:00,909 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [595362424] [2022-04-08 07:25:00,919 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 07:25:00,920 INFO L85 PathProgramCache]: Analyzing trace with hash 1717894843, now seen corresponding path program 2 times [2022-04-08 07:25:00,923 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 07:25:00,924 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1109461194] [2022-04-08 07:25:00,924 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 07:25:00,925 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 07:25:01,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 07:25:01,118 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 07:25:01,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 07:25:01,160 INFO L290 TraceCheckUtils]: 0: Hoare triple {44#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {35#true} is VALID [2022-04-08 07:25:01,160 INFO L290 TraceCheckUtils]: 1: Hoare triple {35#true} assume true; {35#true} is VALID [2022-04-08 07:25:01,161 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {35#true} {35#true} #77#return; {35#true} is VALID [2022-04-08 07:25:01,162 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-08 07:25:01,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 07:25:01,174 INFO L290 TraceCheckUtils]: 0: Hoare triple {35#true} ~cond := #in~cond; {35#true} is VALID [2022-04-08 07:25:01,174 INFO L290 TraceCheckUtils]: 1: Hoare triple {35#true} assume 0 == ~cond;assume false; {36#false} is VALID [2022-04-08 07:25:01,175 INFO L290 TraceCheckUtils]: 2: Hoare triple {36#false} assume true; {36#false} is VALID [2022-04-08 07:25:01,175 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {36#false} {35#true} #69#return; {36#false} is VALID [2022-04-08 07:25:01,176 INFO L272 TraceCheckUtils]: 0: Hoare triple {35#true} call ULTIMATE.init(); {44#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 07:25:01,176 INFO L290 TraceCheckUtils]: 1: Hoare triple {44#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {35#true} is VALID [2022-04-08 07:25:01,177 INFO L290 TraceCheckUtils]: 2: Hoare triple {35#true} assume true; {35#true} is VALID [2022-04-08 07:25:01,177 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {35#true} {35#true} #77#return; {35#true} is VALID [2022-04-08 07:25:01,177 INFO L272 TraceCheckUtils]: 4: Hoare triple {35#true} call #t~ret7 := main(); {35#true} is VALID [2022-04-08 07:25:01,177 INFO L290 TraceCheckUtils]: 5: Hoare triple {35#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {35#true} is VALID [2022-04-08 07:25:01,178 INFO L272 TraceCheckUtils]: 6: Hoare triple {35#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {35#true} is VALID [2022-04-08 07:25:01,178 INFO L290 TraceCheckUtils]: 7: Hoare triple {35#true} ~cond := #in~cond; {35#true} is VALID [2022-04-08 07:25:01,179 INFO L290 TraceCheckUtils]: 8: Hoare triple {35#true} assume 0 == ~cond;assume false; {36#false} is VALID [2022-04-08 07:25:01,179 INFO L290 TraceCheckUtils]: 9: Hoare triple {36#false} assume true; {36#false} is VALID [2022-04-08 07:25:01,179 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {36#false} {35#true} #69#return; {36#false} is VALID [2022-04-08 07:25:01,179 INFO L290 TraceCheckUtils]: 11: Hoare triple {36#false} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {36#false} is VALID [2022-04-08 07:25:01,180 INFO L290 TraceCheckUtils]: 12: Hoare triple {36#false} assume !true; {36#false} is VALID [2022-04-08 07:25:01,180 INFO L272 TraceCheckUtils]: 13: Hoare triple {36#false} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {36#false} is VALID [2022-04-08 07:25:01,180 INFO L290 TraceCheckUtils]: 14: Hoare triple {36#false} ~cond := #in~cond; {36#false} is VALID [2022-04-08 07:25:01,180 INFO L290 TraceCheckUtils]: 15: Hoare triple {36#false} assume 0 == ~cond; {36#false} is VALID [2022-04-08 07:25:01,181 INFO L290 TraceCheckUtils]: 16: Hoare triple {36#false} assume !false; {36#false} is VALID [2022-04-08 07:25:01,181 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 07:25:01,182 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 07:25:01,182 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1109461194] [2022-04-08 07:25:01,182 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1109461194] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 07:25:01,183 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 07:25:01,183 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 07:25:01,185 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 07:25:01,185 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [595362424] [2022-04-08 07:25:01,186 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [595362424] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 07:25:01,186 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 07:25:01,186 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 07:25:01,186 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [897734792] [2022-04-08 07:25:01,187 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 07:25:01,191 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-08 07:25:01,193 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 07:25:01,195 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 07:25:01,214 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 17 edges. 17 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:01,215 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-08 07:25:01,215 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 07:25:01,232 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-08 07:25:01,233 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-08 07:25:01,235 INFO L87 Difference]: Start difference. First operand has 32 states, 20 states have (on average 1.45) internal successors, (29), 21 states have internal predecessors, (29), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 07:25:01,396 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:01,397 INFO L93 Difference]: Finished difference Result 56 states and 77 transitions. [2022-04-08 07:25:01,397 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-08 07:25:01,398 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-08 07:25:01,398 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 07:25:01,399 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 07:25:01,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 77 transitions. [2022-04-08 07:25:01,410 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 07:25:01,422 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 77 transitions. [2022-04-08 07:25:01,422 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 77 transitions. [2022-04-08 07:25:01,517 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 77 edges. 77 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:01,526 INFO L225 Difference]: With dead ends: 56 [2022-04-08 07:25:01,526 INFO L226 Difference]: Without dead ends: 28 [2022-04-08 07:25:01,528 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-08 07:25:01,534 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 07:25:01,535 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 40 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 07:25:01,549 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2022-04-08 07:25:01,567 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 27. [2022-04-08 07:25:01,567 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 07:25:01,568 INFO L82 GeneralOperation]: Start isEquivalent. First operand 28 states. Second operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-08 07:25:01,569 INFO L74 IsIncluded]: Start isIncluded. First operand 28 states. Second operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-08 07:25:01,570 INFO L87 Difference]: Start difference. First operand 28 states. Second operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-08 07:25:01,574 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:01,574 INFO L93 Difference]: Finished difference Result 28 states and 34 transitions. [2022-04-08 07:25:01,574 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 34 transitions. [2022-04-08 07:25:01,575 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:25:01,575 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:25:01,576 INFO L74 IsIncluded]: Start isIncluded. First operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand 28 states. [2022-04-08 07:25:01,576 INFO L87 Difference]: Start difference. First operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand 28 states. [2022-04-08 07:25:01,582 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:01,582 INFO L93 Difference]: Finished difference Result 28 states and 34 transitions. [2022-04-08 07:25:01,585 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 34 transitions. [2022-04-08 07:25:01,585 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:25:01,589 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:25:01,589 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 07:25:01,590 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 07:25:01,591 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-08 07:25:01,593 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 33 transitions. [2022-04-08 07:25:01,594 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 33 transitions. Word has length 17 [2022-04-08 07:25:01,595 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 07:25:01,595 INFO L478 AbstractCegarLoop]: Abstraction has 27 states and 33 transitions. [2022-04-08 07:25:01,595 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 07:25:01,596 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 27 states and 33 transitions. [2022-04-08 07:25:01,636 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 33 edges. 33 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:01,636 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 33 transitions. [2022-04-08 07:25:01,637 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-08 07:25:01,637 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 07:25:01,637 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 07:25:01,638 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-08 07:25:01,638 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 07:25:01,639 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 07:25:01,639 INFO L85 PathProgramCache]: Analyzing trace with hash 444281082, now seen corresponding path program 1 times [2022-04-08 07:25:01,639 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 07:25:01,639 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [777126427] [2022-04-08 07:25:01,647 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 07:25:01,648 INFO L85 PathProgramCache]: Analyzing trace with hash 444281082, now seen corresponding path program 2 times [2022-04-08 07:25:01,648 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 07:25:01,648 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1501224374] [2022-04-08 07:25:01,648 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 07:25:01,649 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 07:25:01,678 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 07:25:01,678 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [151079839] [2022-04-08 07:25:01,678 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 07:25:01,678 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 07:25:01,679 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 07:25:01,684 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-08 07:25:01,685 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-08 07:25:01,733 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 07:25:01,733 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 07:25:01,735 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-08 07:25:01,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 07:25:01,746 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 07:25:01,892 INFO L272 TraceCheckUtils]: 0: Hoare triple {269#true} call ULTIMATE.init(); {269#true} is VALID [2022-04-08 07:25:01,893 INFO L290 TraceCheckUtils]: 1: Hoare triple {269#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {277#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:01,894 INFO L290 TraceCheckUtils]: 2: Hoare triple {277#(<= ~counter~0 0)} assume true; {277#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:01,895 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {277#(<= ~counter~0 0)} {269#true} #77#return; {277#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:01,895 INFO L272 TraceCheckUtils]: 4: Hoare triple {277#(<= ~counter~0 0)} call #t~ret7 := main(); {277#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:01,896 INFO L290 TraceCheckUtils]: 5: Hoare triple {277#(<= ~counter~0 0)} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {277#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:01,896 INFO L272 TraceCheckUtils]: 6: Hoare triple {277#(<= ~counter~0 0)} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {277#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:01,897 INFO L290 TraceCheckUtils]: 7: Hoare triple {277#(<= ~counter~0 0)} ~cond := #in~cond; {277#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:01,897 INFO L290 TraceCheckUtils]: 8: Hoare triple {277#(<= ~counter~0 0)} assume !(0 == ~cond); {277#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:01,898 INFO L290 TraceCheckUtils]: 9: Hoare triple {277#(<= ~counter~0 0)} assume true; {277#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:01,898 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {277#(<= ~counter~0 0)} {277#(<= ~counter~0 0)} #69#return; {277#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:01,899 INFO L290 TraceCheckUtils]: 11: Hoare triple {277#(<= ~counter~0 0)} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {277#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:01,899 INFO L290 TraceCheckUtils]: 12: Hoare triple {277#(<= ~counter~0 0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {311#(<= |main_#t~post6| 0)} is VALID [2022-04-08 07:25:01,900 INFO L290 TraceCheckUtils]: 13: Hoare triple {311#(<= |main_#t~post6| 0)} assume !(#t~post6 < 20);havoc #t~post6; {270#false} is VALID [2022-04-08 07:25:01,900 INFO L272 TraceCheckUtils]: 14: Hoare triple {270#false} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {270#false} is VALID [2022-04-08 07:25:01,900 INFO L290 TraceCheckUtils]: 15: Hoare triple {270#false} ~cond := #in~cond; {270#false} is VALID [2022-04-08 07:25:01,901 INFO L290 TraceCheckUtils]: 16: Hoare triple {270#false} assume 0 == ~cond; {270#false} is VALID [2022-04-08 07:25:01,901 INFO L290 TraceCheckUtils]: 17: Hoare triple {270#false} assume !false; {270#false} is VALID [2022-04-08 07:25:01,901 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 07:25:01,901 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 07:25:01,901 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 07:25:01,902 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1501224374] [2022-04-08 07:25:01,902 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 07:25:01,902 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [151079839] [2022-04-08 07:25:01,902 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [151079839] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 07:25:01,902 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 07:25:01,902 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-08 07:25:01,903 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 07:25:01,903 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [777126427] [2022-04-08 07:25:01,904 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [777126427] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 07:25:01,904 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 07:25:01,904 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-08 07:25:01,904 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [520779828] [2022-04-08 07:25:01,904 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 07:25:01,905 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2022-04-08 07:25:01,905 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 07:25:01,905 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 07:25:01,921 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 18 edges. 18 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:01,921 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-08 07:25:01,921 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 07:25:01,922 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-08 07:25:01,922 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-08 07:25:01,923 INFO L87 Difference]: Start difference. First operand 27 states and 33 transitions. Second operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 07:25:02,018 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:02,018 INFO L93 Difference]: Finished difference Result 37 states and 44 transitions. [2022-04-08 07:25:02,018 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-08 07:25:02,018 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2022-04-08 07:25:02,019 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 07:25:02,019 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 07:25:02,025 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 44 transitions. [2022-04-08 07:25:02,025 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 07:25:02,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 44 transitions. [2022-04-08 07:25:02,028 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 4 states and 44 transitions. [2022-04-08 07:25:02,064 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:02,066 INFO L225 Difference]: With dead ends: 37 [2022-04-08 07:25:02,066 INFO L226 Difference]: Without dead ends: 29 [2022-04-08 07:25:02,067 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-08 07:25:02,070 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 0 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 07:25:02,073 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 81 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 07:25:02,075 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2022-04-08 07:25:02,091 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2022-04-08 07:25:02,091 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 07:25:02,092 INFO L82 GeneralOperation]: Start isEquivalent. First operand 29 states. Second operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-08 07:25:02,093 INFO L74 IsIncluded]: Start isIncluded. First operand 29 states. Second operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-08 07:25:02,093 INFO L87 Difference]: Start difference. First operand 29 states. Second operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-08 07:25:02,096 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:02,096 INFO L93 Difference]: Finished difference Result 29 states and 35 transitions. [2022-04-08 07:25:02,096 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2022-04-08 07:25:02,097 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:25:02,097 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:25:02,099 INFO L74 IsIncluded]: Start isIncluded. First operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand 29 states. [2022-04-08 07:25:02,099 INFO L87 Difference]: Start difference. First operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand 29 states. [2022-04-08 07:25:02,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:02,124 INFO L93 Difference]: Finished difference Result 29 states and 35 transitions. [2022-04-08 07:25:02,125 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2022-04-08 07:25:02,126 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:25:02,126 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:25:02,126 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 07:25:02,126 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 07:25:02,127 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-08 07:25:02,129 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 35 transitions. [2022-04-08 07:25:02,129 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 35 transitions. Word has length 18 [2022-04-08 07:25:02,129 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 07:25:02,129 INFO L478 AbstractCegarLoop]: Abstraction has 29 states and 35 transitions. [2022-04-08 07:25:02,130 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 07:25:02,130 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 29 states and 35 transitions. [2022-04-08 07:25:02,192 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 35 edges. 35 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:02,192 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2022-04-08 07:25:02,193 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-08 07:25:02,193 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 07:25:02,193 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 07:25:02,220 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-08 07:25:02,409 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-08 07:25:02,409 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 07:25:02,410 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 07:25:02,410 INFO L85 PathProgramCache]: Analyzing trace with hash 446068542, now seen corresponding path program 1 times [2022-04-08 07:25:02,410 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 07:25:02,410 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [517702807] [2022-04-08 07:25:02,411 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 07:25:02,411 INFO L85 PathProgramCache]: Analyzing trace with hash 446068542, now seen corresponding path program 2 times [2022-04-08 07:25:02,411 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 07:25:02,411 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [425646774] [2022-04-08 07:25:02,411 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 07:25:02,411 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 07:25:02,430 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 07:25:02,431 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [503835432] [2022-04-08 07:25:02,431 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 07:25:02,431 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 07:25:02,431 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 07:25:02,433 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-08 07:25:02,434 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-08 07:25:02,472 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 07:25:02,472 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 07:25:02,473 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 15 conjunts are in the unsatisfiable core [2022-04-08 07:25:02,481 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 07:25:02,481 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 07:25:02,633 INFO L272 TraceCheckUtils]: 0: Hoare triple {516#true} call ULTIMATE.init(); {516#true} is VALID [2022-04-08 07:25:02,634 INFO L290 TraceCheckUtils]: 1: Hoare triple {516#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {516#true} is VALID [2022-04-08 07:25:02,634 INFO L290 TraceCheckUtils]: 2: Hoare triple {516#true} assume true; {516#true} is VALID [2022-04-08 07:25:02,634 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {516#true} {516#true} #77#return; {516#true} is VALID [2022-04-08 07:25:02,634 INFO L272 TraceCheckUtils]: 4: Hoare triple {516#true} call #t~ret7 := main(); {516#true} is VALID [2022-04-08 07:25:02,634 INFO L290 TraceCheckUtils]: 5: Hoare triple {516#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {516#true} is VALID [2022-04-08 07:25:02,635 INFO L272 TraceCheckUtils]: 6: Hoare triple {516#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {516#true} is VALID [2022-04-08 07:25:02,635 INFO L290 TraceCheckUtils]: 7: Hoare triple {516#true} ~cond := #in~cond; {516#true} is VALID [2022-04-08 07:25:02,635 INFO L290 TraceCheckUtils]: 8: Hoare triple {516#true} assume !(0 == ~cond); {516#true} is VALID [2022-04-08 07:25:02,635 INFO L290 TraceCheckUtils]: 9: Hoare triple {516#true} assume true; {516#true} is VALID [2022-04-08 07:25:02,635 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {516#true} {516#true} #69#return; {516#true} is VALID [2022-04-08 07:25:02,636 INFO L290 TraceCheckUtils]: 11: Hoare triple {516#true} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {554#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-08 07:25:02,637 INFO L290 TraceCheckUtils]: 12: Hoare triple {554#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {554#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-08 07:25:02,638 INFO L290 TraceCheckUtils]: 13: Hoare triple {554#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} assume !!(#t~post6 < 20);havoc #t~post6; {554#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-08 07:25:02,639 INFO L272 TraceCheckUtils]: 14: Hoare triple {554#(and (= main_~b~0 main_~y~0) (= main_~q~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {564#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 07:25:02,639 INFO L290 TraceCheckUtils]: 15: Hoare triple {564#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {568#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 07:25:02,640 INFO L290 TraceCheckUtils]: 16: Hoare triple {568#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {517#false} is VALID [2022-04-08 07:25:02,640 INFO L290 TraceCheckUtils]: 17: Hoare triple {517#false} assume !false; {517#false} is VALID [2022-04-08 07:25:02,640 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 07:25:02,641 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 07:25:02,641 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 07:25:02,641 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [425646774] [2022-04-08 07:25:02,641 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 07:25:02,641 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [503835432] [2022-04-08 07:25:02,641 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [503835432] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 07:25:02,641 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 07:25:02,642 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 07:25:02,642 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 07:25:02,642 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [517702807] [2022-04-08 07:25:02,642 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [517702807] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 07:25:02,642 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 07:25:02,642 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 07:25:02,642 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [778973107] [2022-04-08 07:25:02,643 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 07:25:02,643 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-08 07:25:02,643 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 07:25:02,643 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 07:25:02,660 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 18 edges. 18 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:02,661 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 07:25:02,661 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 07:25:02,661 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 07:25:02,661 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-08 07:25:02,662 INFO L87 Difference]: Start difference. First operand 29 states and 35 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 07:25:02,845 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:02,845 INFO L93 Difference]: Finished difference Result 42 states and 53 transitions. [2022-04-08 07:25:02,845 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 07:25:02,845 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-08 07:25:02,846 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 07:25:02,846 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 07:25:02,847 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 53 transitions. [2022-04-08 07:25:02,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 07:25:02,849 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 53 transitions. [2022-04-08 07:25:02,849 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 53 transitions. [2022-04-08 07:25:02,903 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 53 edges. 53 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:02,904 INFO L225 Difference]: With dead ends: 42 [2022-04-08 07:25:02,904 INFO L226 Difference]: Without dead ends: 40 [2022-04-08 07:25:02,905 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-08 07:25:02,906 INFO L913 BasicCegarLoop]: 24 mSDtfsCounter, 9 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-08 07:25:02,906 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 83 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-08 07:25:02,906 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2022-04-08 07:25:02,922 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 34. [2022-04-08 07:25:02,922 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 07:25:02,922 INFO L82 GeneralOperation]: Start isEquivalent. First operand 40 states. Second operand has 34 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 24 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-08 07:25:02,923 INFO L74 IsIncluded]: Start isIncluded. First operand 40 states. Second operand has 34 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 24 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-08 07:25:02,923 INFO L87 Difference]: Start difference. First operand 40 states. Second operand has 34 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 24 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-08 07:25:02,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:02,925 INFO L93 Difference]: Finished difference Result 40 states and 51 transitions. [2022-04-08 07:25:02,925 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 51 transitions. [2022-04-08 07:25:02,925 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:25:02,925 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:25:02,926 INFO L74 IsIncluded]: Start isIncluded. First operand has 34 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 24 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) Second operand 40 states. [2022-04-08 07:25:02,926 INFO L87 Difference]: Start difference. First operand has 34 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 24 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) Second operand 40 states. [2022-04-08 07:25:02,928 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:02,928 INFO L93 Difference]: Finished difference Result 40 states and 51 transitions. [2022-04-08 07:25:02,928 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 51 transitions. [2022-04-08 07:25:02,928 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:25:02,929 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:25:02,929 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 07:25:02,929 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 07:25:02,929 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 24 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-08 07:25:02,930 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 40 transitions. [2022-04-08 07:25:02,930 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 40 transitions. Word has length 18 [2022-04-08 07:25:02,931 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 07:25:02,931 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 40 transitions. [2022-04-08 07:25:02,931 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-08 07:25:02,931 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 34 states and 40 transitions. [2022-04-08 07:25:02,987 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 40 edges. 40 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:02,987 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 40 transitions. [2022-04-08 07:25:02,987 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-08 07:25:02,988 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 07:25:02,988 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 07:25:03,019 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-08 07:25:03,198 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-08 07:25:03,199 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 07:25:03,199 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 07:25:03,199 INFO L85 PathProgramCache]: Analyzing trace with hash -1308579644, now seen corresponding path program 1 times [2022-04-08 07:25:03,199 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 07:25:03,200 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [972932330] [2022-04-08 07:25:03,200 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 07:25:03,200 INFO L85 PathProgramCache]: Analyzing trace with hash -1308579644, now seen corresponding path program 2 times [2022-04-08 07:25:03,201 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 07:25:03,201 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [278031593] [2022-04-08 07:25:03,201 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 07:25:03,201 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 07:25:03,212 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 07:25:03,213 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1705562095] [2022-04-08 07:25:03,213 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 07:25:03,213 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 07:25:03,213 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 07:25:03,214 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-08 07:25:03,216 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-08 07:25:03,253 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 07:25:03,253 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 07:25:03,254 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 15 conjunts are in the unsatisfiable core [2022-04-08 07:25:03,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 07:25:03,264 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 07:25:12,194 INFO L272 TraceCheckUtils]: 0: Hoare triple {808#true} call ULTIMATE.init(); {808#true} is VALID [2022-04-08 07:25:12,194 INFO L290 TraceCheckUtils]: 1: Hoare triple {808#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {808#true} is VALID [2022-04-08 07:25:12,194 INFO L290 TraceCheckUtils]: 2: Hoare triple {808#true} assume true; {808#true} is VALID [2022-04-08 07:25:12,195 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {808#true} {808#true} #77#return; {808#true} is VALID [2022-04-08 07:25:12,195 INFO L272 TraceCheckUtils]: 4: Hoare triple {808#true} call #t~ret7 := main(); {808#true} is VALID [2022-04-08 07:25:12,195 INFO L290 TraceCheckUtils]: 5: Hoare triple {808#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {808#true} is VALID [2022-04-08 07:25:12,195 INFO L272 TraceCheckUtils]: 6: Hoare triple {808#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {808#true} is VALID [2022-04-08 07:25:12,196 INFO L290 TraceCheckUtils]: 7: Hoare triple {808#true} ~cond := #in~cond; {834#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-08 07:25:12,196 INFO L290 TraceCheckUtils]: 8: Hoare triple {834#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {838#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-08 07:25:12,197 INFO L290 TraceCheckUtils]: 9: Hoare triple {838#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {838#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-08 07:25:12,199 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {838#(not (= |assume_abort_if_not_#in~cond| 0))} {808#true} #69#return; {845#(<= 1 main_~y~0)} is VALID [2022-04-08 07:25:12,199 INFO L290 TraceCheckUtils]: 11: Hoare triple {845#(<= 1 main_~y~0)} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {849#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} is VALID [2022-04-08 07:25:12,200 INFO L290 TraceCheckUtils]: 12: Hoare triple {849#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {849#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} is VALID [2022-04-08 07:25:12,201 INFO L290 TraceCheckUtils]: 13: Hoare triple {849#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} assume !!(#t~post6 < 20);havoc #t~post6; {849#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} is VALID [2022-04-08 07:25:12,201 INFO L272 TraceCheckUtils]: 14: Hoare triple {849#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {808#true} is VALID [2022-04-08 07:25:12,201 INFO L290 TraceCheckUtils]: 15: Hoare triple {808#true} ~cond := #in~cond; {862#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-08 07:25:12,202 INFO L290 TraceCheckUtils]: 16: Hoare triple {862#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {866#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 07:25:12,202 INFO L290 TraceCheckUtils]: 17: Hoare triple {866#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {866#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 07:25:14,205 WARN L284 TraceCheckUtils]: 18: Hoare quadruple {866#(not (= |__VERIFIER_assert_#in~cond| 0))} {849#(and (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} #71#return; {873#(and (or (and (= (mod (+ (* main_~y~0 main_~x~0) (* (- 1) main_~q~0)) (* main_~b~0 main_~a~0)) 0) (not (= main_~a~0 0))) (= (+ (* main_~y~0 main_~x~0) (* (- 1) main_~q~0)) 0)) (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} is UNKNOWN [2022-04-08 07:25:14,208 INFO L290 TraceCheckUtils]: 19: Hoare triple {873#(and (or (and (= (mod (+ (* main_~y~0 main_~x~0) (* (- 1) main_~q~0)) (* main_~b~0 main_~a~0)) 0) (not (= main_~a~0 0))) (= (+ (* main_~y~0 main_~x~0) (* (- 1) main_~q~0)) 0)) (<= main_~y~0 main_~b~0) (<= 1 main_~y~0))} assume !(0 != ~a~0 && 0 != ~b~0); {877#(and (= main_~q~0 (* main_~y~0 main_~x~0)) (<= 1 main_~y~0))} is VALID [2022-04-08 07:25:14,209 INFO L272 TraceCheckUtils]: 20: Hoare triple {877#(and (= main_~q~0 (* main_~y~0 main_~x~0)) (<= 1 main_~y~0))} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {881#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 07:25:14,210 INFO L290 TraceCheckUtils]: 21: Hoare triple {881#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {885#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 07:25:14,212 INFO L290 TraceCheckUtils]: 22: Hoare triple {885#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {809#false} is VALID [2022-04-08 07:25:14,212 INFO L290 TraceCheckUtils]: 23: Hoare triple {809#false} assume !false; {809#false} is VALID [2022-04-08 07:25:14,213 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 07:25:14,213 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-08 07:25:27,693 INFO L290 TraceCheckUtils]: 23: Hoare triple {809#false} assume !false; {809#false} is VALID [2022-04-08 07:25:27,693 INFO L290 TraceCheckUtils]: 22: Hoare triple {885#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {809#false} is VALID [2022-04-08 07:25:27,694 INFO L290 TraceCheckUtils]: 21: Hoare triple {881#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {885#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 07:25:27,695 INFO L272 TraceCheckUtils]: 20: Hoare triple {901#(= main_~q~0 (* main_~y~0 main_~x~0))} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {881#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 07:25:27,695 INFO L290 TraceCheckUtils]: 19: Hoare triple {905#(or (= main_~q~0 (* main_~y~0 main_~x~0)) (and (not (= main_~b~0 0)) (not (= main_~a~0 0))))} assume !(0 != ~a~0 && 0 != ~b~0); {901#(= main_~q~0 (* main_~y~0 main_~x~0))} is VALID [2022-04-08 07:25:27,698 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {866#(not (= |__VERIFIER_assert_#in~cond| 0))} {808#true} #71#return; {905#(or (= main_~q~0 (* main_~y~0 main_~x~0)) (and (not (= main_~b~0 0)) (not (= main_~a~0 0))))} is VALID [2022-04-08 07:25:27,698 INFO L290 TraceCheckUtils]: 17: Hoare triple {866#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {866#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 07:25:27,699 INFO L290 TraceCheckUtils]: 16: Hoare triple {918#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {866#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 07:25:27,699 INFO L290 TraceCheckUtils]: 15: Hoare triple {808#true} ~cond := #in~cond; {918#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 07:25:27,699 INFO L272 TraceCheckUtils]: 14: Hoare triple {808#true} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {808#true} is VALID [2022-04-08 07:25:27,700 INFO L290 TraceCheckUtils]: 13: Hoare triple {808#true} assume !!(#t~post6 < 20);havoc #t~post6; {808#true} is VALID [2022-04-08 07:25:27,700 INFO L290 TraceCheckUtils]: 12: Hoare triple {808#true} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {808#true} is VALID [2022-04-08 07:25:27,700 INFO L290 TraceCheckUtils]: 11: Hoare triple {808#true} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {808#true} is VALID [2022-04-08 07:25:27,700 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {808#true} {808#true} #69#return; {808#true} is VALID [2022-04-08 07:25:27,700 INFO L290 TraceCheckUtils]: 9: Hoare triple {808#true} assume true; {808#true} is VALID [2022-04-08 07:25:27,700 INFO L290 TraceCheckUtils]: 8: Hoare triple {808#true} assume !(0 == ~cond); {808#true} is VALID [2022-04-08 07:25:27,701 INFO L290 TraceCheckUtils]: 7: Hoare triple {808#true} ~cond := #in~cond; {808#true} is VALID [2022-04-08 07:25:27,701 INFO L272 TraceCheckUtils]: 6: Hoare triple {808#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {808#true} is VALID [2022-04-08 07:25:27,701 INFO L290 TraceCheckUtils]: 5: Hoare triple {808#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {808#true} is VALID [2022-04-08 07:25:27,701 INFO L272 TraceCheckUtils]: 4: Hoare triple {808#true} call #t~ret7 := main(); {808#true} is VALID [2022-04-08 07:25:27,701 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {808#true} {808#true} #77#return; {808#true} is VALID [2022-04-08 07:25:27,701 INFO L290 TraceCheckUtils]: 2: Hoare triple {808#true} assume true; {808#true} is VALID [2022-04-08 07:25:27,702 INFO L290 TraceCheckUtils]: 1: Hoare triple {808#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {808#true} is VALID [2022-04-08 07:25:27,702 INFO L272 TraceCheckUtils]: 0: Hoare triple {808#true} call ULTIMATE.init(); {808#true} is VALID [2022-04-08 07:25:27,702 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 07:25:27,702 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 07:25:27,702 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [278031593] [2022-04-08 07:25:27,702 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 07:25:27,702 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1705562095] [2022-04-08 07:25:27,703 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1705562095] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-08 07:25:27,703 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-08 07:25:27,703 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 8] total 15 [2022-04-08 07:25:27,703 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 07:25:27,703 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [972932330] [2022-04-08 07:25:27,703 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [972932330] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 07:25:27,703 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 07:25:27,704 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-08 07:25:27,704 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [233411879] [2022-04-08 07:25:27,704 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 07:25:27,704 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 9 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2022-04-08 07:25:27,704 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 07:25:27,705 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 12 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 9 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 07:25:29,727 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 24 edges. 23 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:29,727 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-08 07:25:29,727 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 07:25:29,728 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-08 07:25:29,728 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2022-04-08 07:25:29,728 INFO L87 Difference]: Start difference. First operand 34 states and 40 transitions. Second operand has 12 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 9 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 07:25:32,991 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:32,992 INFO L93 Difference]: Finished difference Result 50 states and 63 transitions. [2022-04-08 07:25:32,992 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-08 07:25:32,992 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 9 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2022-04-08 07:25:32,992 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 07:25:32,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 9 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 07:25:32,995 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 60 transitions. [2022-04-08 07:25:32,995 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 9 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 07:25:32,997 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 60 transitions. [2022-04-08 07:25:32,997 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 13 states and 60 transitions. [2022-04-08 07:25:35,061 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 60 edges. 59 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:35,063 INFO L225 Difference]: With dead ends: 50 [2022-04-08 07:25:35,063 INFO L226 Difference]: Without dead ends: 48 [2022-04-08 07:25:35,064 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 33 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=64, Invalid=278, Unknown=0, NotChecked=0, Total=342 [2022-04-08 07:25:35,064 INFO L913 BasicCegarLoop]: 20 mSDtfsCounter, 36 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 204 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 221 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 204 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2022-04-08 07:25:35,065 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 130 Invalid, 221 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 204 Invalid, 0 Unknown, 0 Unchecked, 1.6s Time] [2022-04-08 07:25:35,065 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-04-08 07:25:35,106 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 45. [2022-04-08 07:25:35,106 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 07:25:35,106 INFO L82 GeneralOperation]: Start isEquivalent. First operand 48 states. Second operand has 45 states, 30 states have (on average 1.3333333333333333) internal successors, (40), 33 states have internal predecessors, (40), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 07:25:35,108 INFO L74 IsIncluded]: Start isIncluded. First operand 48 states. Second operand has 45 states, 30 states have (on average 1.3333333333333333) internal successors, (40), 33 states have internal predecessors, (40), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 07:25:35,108 INFO L87 Difference]: Start difference. First operand 48 states. Second operand has 45 states, 30 states have (on average 1.3333333333333333) internal successors, (40), 33 states have internal predecessors, (40), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 07:25:35,110 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:35,111 INFO L93 Difference]: Finished difference Result 48 states and 61 transitions. [2022-04-08 07:25:35,111 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 61 transitions. [2022-04-08 07:25:35,111 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:25:35,111 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:25:35,112 INFO L74 IsIncluded]: Start isIncluded. First operand has 45 states, 30 states have (on average 1.3333333333333333) internal successors, (40), 33 states have internal predecessors, (40), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) Second operand 48 states. [2022-04-08 07:25:35,112 INFO L87 Difference]: Start difference. First operand has 45 states, 30 states have (on average 1.3333333333333333) internal successors, (40), 33 states have internal predecessors, (40), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) Second operand 48 states. [2022-04-08 07:25:35,114 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:35,115 INFO L93 Difference]: Finished difference Result 48 states and 61 transitions. [2022-04-08 07:25:35,115 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 61 transitions. [2022-04-08 07:25:35,115 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:25:35,115 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:25:35,116 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 07:25:35,116 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 07:25:35,116 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 30 states have (on average 1.3333333333333333) internal successors, (40), 33 states have internal predecessors, (40), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 07:25:35,118 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 56 transitions. [2022-04-08 07:25:35,118 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 56 transitions. Word has length 24 [2022-04-08 07:25:35,118 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 07:25:35,118 INFO L478 AbstractCegarLoop]: Abstraction has 45 states and 56 transitions. [2022-04-08 07:25:35,118 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 9 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 07:25:35,119 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 45 states and 56 transitions. [2022-04-08 07:25:37,183 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 56 edges. 55 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:37,183 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 56 transitions. [2022-04-08 07:25:37,184 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-04-08 07:25:37,184 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 07:25:37,184 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 07:25:37,212 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-08 07:25:37,385 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-08 07:25:37,385 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 07:25:37,385 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 07:25:37,385 INFO L85 PathProgramCache]: Analyzing trace with hash 1797927234, now seen corresponding path program 1 times [2022-04-08 07:25:37,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 07:25:37,386 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [584366002] [2022-04-08 07:25:43,473 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-08 07:25:43,474 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-08 07:25:43,474 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 07:25:43,474 INFO L85 PathProgramCache]: Analyzing trace with hash 1797927234, now seen corresponding path program 2 times [2022-04-08 07:25:43,474 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 07:25:43,474 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1212951005] [2022-04-08 07:25:43,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 07:25:43,474 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 07:25:43,488 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 07:25:43,488 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [471997032] [2022-04-08 07:25:43,488 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 07:25:43,488 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 07:25:43,488 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 07:25:43,491 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-08 07:25:43,496 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-08 07:25:43,537 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 07:25:43,537 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 07:25:43,538 INFO L263 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-08 07:25:43,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 07:25:43,554 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 07:25:43,745 INFO L272 TraceCheckUtils]: 0: Hoare triple {1260#true} call ULTIMATE.init(); {1260#true} is VALID [2022-04-08 07:25:43,747 INFO L290 TraceCheckUtils]: 1: Hoare triple {1260#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1268#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:43,748 INFO L290 TraceCheckUtils]: 2: Hoare triple {1268#(<= ~counter~0 0)} assume true; {1268#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:43,748 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1268#(<= ~counter~0 0)} {1260#true} #77#return; {1268#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:43,749 INFO L272 TraceCheckUtils]: 4: Hoare triple {1268#(<= ~counter~0 0)} call #t~ret7 := main(); {1268#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:43,750 INFO L290 TraceCheckUtils]: 5: Hoare triple {1268#(<= ~counter~0 0)} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {1268#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:43,759 INFO L272 TraceCheckUtils]: 6: Hoare triple {1268#(<= ~counter~0 0)} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1268#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:43,760 INFO L290 TraceCheckUtils]: 7: Hoare triple {1268#(<= ~counter~0 0)} ~cond := #in~cond; {1268#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:43,760 INFO L290 TraceCheckUtils]: 8: Hoare triple {1268#(<= ~counter~0 0)} assume !(0 == ~cond); {1268#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:43,761 INFO L290 TraceCheckUtils]: 9: Hoare triple {1268#(<= ~counter~0 0)} assume true; {1268#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:43,761 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1268#(<= ~counter~0 0)} {1268#(<= ~counter~0 0)} #69#return; {1268#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:43,762 INFO L290 TraceCheckUtils]: 11: Hoare triple {1268#(<= ~counter~0 0)} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {1268#(<= ~counter~0 0)} is VALID [2022-04-08 07:25:43,763 INFO L290 TraceCheckUtils]: 12: Hoare triple {1268#(<= ~counter~0 0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1302#(<= ~counter~0 1)} is VALID [2022-04-08 07:25:43,763 INFO L290 TraceCheckUtils]: 13: Hoare triple {1302#(<= ~counter~0 1)} assume !!(#t~post6 < 20);havoc #t~post6; {1302#(<= ~counter~0 1)} is VALID [2022-04-08 07:25:43,764 INFO L272 TraceCheckUtils]: 14: Hoare triple {1302#(<= ~counter~0 1)} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {1302#(<= ~counter~0 1)} is VALID [2022-04-08 07:25:43,764 INFO L290 TraceCheckUtils]: 15: Hoare triple {1302#(<= ~counter~0 1)} ~cond := #in~cond; {1302#(<= ~counter~0 1)} is VALID [2022-04-08 07:25:43,765 INFO L290 TraceCheckUtils]: 16: Hoare triple {1302#(<= ~counter~0 1)} assume !(0 == ~cond); {1302#(<= ~counter~0 1)} is VALID [2022-04-08 07:25:43,765 INFO L290 TraceCheckUtils]: 17: Hoare triple {1302#(<= ~counter~0 1)} assume true; {1302#(<= ~counter~0 1)} is VALID [2022-04-08 07:25:43,766 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {1302#(<= ~counter~0 1)} {1302#(<= ~counter~0 1)} #71#return; {1302#(<= ~counter~0 1)} is VALID [2022-04-08 07:25:43,766 INFO L290 TraceCheckUtils]: 19: Hoare triple {1302#(<= ~counter~0 1)} assume !!(0 != ~a~0 && 0 != ~b~0); {1302#(<= ~counter~0 1)} is VALID [2022-04-08 07:25:43,767 INFO L290 TraceCheckUtils]: 20: Hoare triple {1302#(<= ~counter~0 1)} assume 0 == (if ~a~0 < 0 && 0 != ~a~0 % 2 then ~a~0 % 2 - 2 else ~a~0 % 2) && 0 == (if ~b~0 < 0 && 0 != ~b~0 % 2 then ~b~0 % 2 - 2 else ~b~0 % 2);~a~0 := (if ~a~0 < 0 && 0 != ~a~0 % 2 then 1 + ~a~0 / 2 else ~a~0 / 2);~b~0 := (if ~b~0 < 0 && 0 != ~b~0 % 2 then 1 + ~b~0 / 2 else ~b~0 / 2);~p~0 := 4 * ~p~0; {1302#(<= ~counter~0 1)} is VALID [2022-04-08 07:25:43,767 INFO L290 TraceCheckUtils]: 21: Hoare triple {1302#(<= ~counter~0 1)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1330#(<= |main_#t~post6| 1)} is VALID [2022-04-08 07:25:43,768 INFO L290 TraceCheckUtils]: 22: Hoare triple {1330#(<= |main_#t~post6| 1)} assume !(#t~post6 < 20);havoc #t~post6; {1261#false} is VALID [2022-04-08 07:25:43,768 INFO L272 TraceCheckUtils]: 23: Hoare triple {1261#false} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {1261#false} is VALID [2022-04-08 07:25:43,768 INFO L290 TraceCheckUtils]: 24: Hoare triple {1261#false} ~cond := #in~cond; {1261#false} is VALID [2022-04-08 07:25:43,768 INFO L290 TraceCheckUtils]: 25: Hoare triple {1261#false} assume 0 == ~cond; {1261#false} is VALID [2022-04-08 07:25:43,768 INFO L290 TraceCheckUtils]: 26: Hoare triple {1261#false} assume !false; {1261#false} is VALID [2022-04-08 07:25:43,769 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 07:25:43,769 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-08 07:25:43,922 INFO L290 TraceCheckUtils]: 26: Hoare triple {1261#false} assume !false; {1261#false} is VALID [2022-04-08 07:25:43,923 INFO L290 TraceCheckUtils]: 25: Hoare triple {1261#false} assume 0 == ~cond; {1261#false} is VALID [2022-04-08 07:25:43,923 INFO L290 TraceCheckUtils]: 24: Hoare triple {1261#false} ~cond := #in~cond; {1261#false} is VALID [2022-04-08 07:25:43,923 INFO L272 TraceCheckUtils]: 23: Hoare triple {1261#false} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {1261#false} is VALID [2022-04-08 07:25:43,924 INFO L290 TraceCheckUtils]: 22: Hoare triple {1358#(< |main_#t~post6| 20)} assume !(#t~post6 < 20);havoc #t~post6; {1261#false} is VALID [2022-04-08 07:25:43,924 INFO L290 TraceCheckUtils]: 21: Hoare triple {1362#(< ~counter~0 20)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1358#(< |main_#t~post6| 20)} is VALID [2022-04-08 07:25:43,925 INFO L290 TraceCheckUtils]: 20: Hoare triple {1362#(< ~counter~0 20)} assume 0 == (if ~a~0 < 0 && 0 != ~a~0 % 2 then ~a~0 % 2 - 2 else ~a~0 % 2) && 0 == (if ~b~0 < 0 && 0 != ~b~0 % 2 then ~b~0 % 2 - 2 else ~b~0 % 2);~a~0 := (if ~a~0 < 0 && 0 != ~a~0 % 2 then 1 + ~a~0 / 2 else ~a~0 / 2);~b~0 := (if ~b~0 < 0 && 0 != ~b~0 % 2 then 1 + ~b~0 / 2 else ~b~0 / 2);~p~0 := 4 * ~p~0; {1362#(< ~counter~0 20)} is VALID [2022-04-08 07:25:43,925 INFO L290 TraceCheckUtils]: 19: Hoare triple {1362#(< ~counter~0 20)} assume !!(0 != ~a~0 && 0 != ~b~0); {1362#(< ~counter~0 20)} is VALID [2022-04-08 07:25:43,926 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {1260#true} {1362#(< ~counter~0 20)} #71#return; {1362#(< ~counter~0 20)} is VALID [2022-04-08 07:25:43,926 INFO L290 TraceCheckUtils]: 17: Hoare triple {1260#true} assume true; {1260#true} is VALID [2022-04-08 07:25:43,926 INFO L290 TraceCheckUtils]: 16: Hoare triple {1260#true} assume !(0 == ~cond); {1260#true} is VALID [2022-04-08 07:25:43,927 INFO L290 TraceCheckUtils]: 15: Hoare triple {1260#true} ~cond := #in~cond; {1260#true} is VALID [2022-04-08 07:25:43,927 INFO L272 TraceCheckUtils]: 14: Hoare triple {1362#(< ~counter~0 20)} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {1260#true} is VALID [2022-04-08 07:25:43,927 INFO L290 TraceCheckUtils]: 13: Hoare triple {1362#(< ~counter~0 20)} assume !!(#t~post6 < 20);havoc #t~post6; {1362#(< ~counter~0 20)} is VALID [2022-04-08 07:25:43,928 INFO L290 TraceCheckUtils]: 12: Hoare triple {1390#(< ~counter~0 19)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1362#(< ~counter~0 20)} is VALID [2022-04-08 07:25:43,928 INFO L290 TraceCheckUtils]: 11: Hoare triple {1390#(< ~counter~0 19)} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {1390#(< ~counter~0 19)} is VALID [2022-04-08 07:25:43,929 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1260#true} {1390#(< ~counter~0 19)} #69#return; {1390#(< ~counter~0 19)} is VALID [2022-04-08 07:25:43,929 INFO L290 TraceCheckUtils]: 9: Hoare triple {1260#true} assume true; {1260#true} is VALID [2022-04-08 07:25:43,929 INFO L290 TraceCheckUtils]: 8: Hoare triple {1260#true} assume !(0 == ~cond); {1260#true} is VALID [2022-04-08 07:25:43,929 INFO L290 TraceCheckUtils]: 7: Hoare triple {1260#true} ~cond := #in~cond; {1260#true} is VALID [2022-04-08 07:25:43,929 INFO L272 TraceCheckUtils]: 6: Hoare triple {1390#(< ~counter~0 19)} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1260#true} is VALID [2022-04-08 07:25:43,930 INFO L290 TraceCheckUtils]: 5: Hoare triple {1390#(< ~counter~0 19)} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {1390#(< ~counter~0 19)} is VALID [2022-04-08 07:25:43,930 INFO L272 TraceCheckUtils]: 4: Hoare triple {1390#(< ~counter~0 19)} call #t~ret7 := main(); {1390#(< ~counter~0 19)} is VALID [2022-04-08 07:25:43,931 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1390#(< ~counter~0 19)} {1260#true} #77#return; {1390#(< ~counter~0 19)} is VALID [2022-04-08 07:25:43,931 INFO L290 TraceCheckUtils]: 2: Hoare triple {1390#(< ~counter~0 19)} assume true; {1390#(< ~counter~0 19)} is VALID [2022-04-08 07:25:43,932 INFO L290 TraceCheckUtils]: 1: Hoare triple {1260#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1390#(< ~counter~0 19)} is VALID [2022-04-08 07:25:43,932 INFO L272 TraceCheckUtils]: 0: Hoare triple {1260#true} call ULTIMATE.init(); {1260#true} is VALID [2022-04-08 07:25:43,932 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 07:25:43,932 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 07:25:43,933 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1212951005] [2022-04-08 07:25:43,933 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 07:25:43,933 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [471997032] [2022-04-08 07:25:43,933 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [471997032] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-08 07:25:43,933 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-08 07:25:43,933 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-04-08 07:25:43,933 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 07:25:43,934 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [584366002] [2022-04-08 07:25:43,934 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [584366002] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 07:25:43,934 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 07:25:43,934 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 07:25:43,934 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1631412348] [2022-04-08 07:25:43,934 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 07:25:43,935 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 4 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Word has length 27 [2022-04-08 07:25:43,935 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 07:25:43,935 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 4 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-08 07:25:43,958 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 27 edges. 27 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:43,958 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 07:25:43,959 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 07:25:43,959 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 07:25:43,959 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-04-08 07:25:43,960 INFO L87 Difference]: Start difference. First operand 45 states and 56 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 4 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-08 07:25:44,139 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:44,139 INFO L93 Difference]: Finished difference Result 73 states and 89 transitions. [2022-04-08 07:25:44,139 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-08 07:25:44,140 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 4 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Word has length 27 [2022-04-08 07:25:44,140 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 07:25:44,140 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 4 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-08 07:25:44,142 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 64 transitions. [2022-04-08 07:25:44,142 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 4 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-08 07:25:44,144 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 64 transitions. [2022-04-08 07:25:44,144 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 64 transitions. [2022-04-08 07:25:44,196 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-08 07:25:44,198 INFO L225 Difference]: With dead ends: 73 [2022-04-08 07:25:44,198 INFO L226 Difference]: Without dead ends: 63 [2022-04-08 07:25:44,198 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 47 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-04-08 07:25:44,199 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 17 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 07:25:44,199 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 108 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 07:25:44,200 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-04-08 07:25:44,276 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 61. [2022-04-08 07:25:44,276 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 07:25:44,277 INFO L82 GeneralOperation]: Start isEquivalent. First operand 63 states. Second operand has 61 states, 43 states have (on average 1.3255813953488371) internal successors, (57), 45 states have internal predecessors, (57), 11 states have call successors, (11), 8 states have call predecessors, (11), 6 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-08 07:25:44,277 INFO L74 IsIncluded]: Start isIncluded. First operand 63 states. Second operand has 61 states, 43 states have (on average 1.3255813953488371) internal successors, (57), 45 states have internal predecessors, (57), 11 states have call successors, (11), 8 states have call predecessors, (11), 6 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-08 07:25:44,278 INFO L87 Difference]: Start difference. First operand 63 states. Second operand has 61 states, 43 states have (on average 1.3255813953488371) internal successors, (57), 45 states have internal predecessors, (57), 11 states have call successors, (11), 8 states have call predecessors, (11), 6 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-08 07:25:44,285 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:44,285 INFO L93 Difference]: Finished difference Result 63 states and 77 transitions. [2022-04-08 07:25:44,286 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 77 transitions. [2022-04-08 07:25:44,288 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:25:44,288 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:25:44,289 INFO L74 IsIncluded]: Start isIncluded. First operand has 61 states, 43 states have (on average 1.3255813953488371) internal successors, (57), 45 states have internal predecessors, (57), 11 states have call successors, (11), 8 states have call predecessors, (11), 6 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) Second operand 63 states. [2022-04-08 07:25:44,291 INFO L87 Difference]: Start difference. First operand has 61 states, 43 states have (on average 1.3255813953488371) internal successors, (57), 45 states have internal predecessors, (57), 11 states have call successors, (11), 8 states have call predecessors, (11), 6 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) Second operand 63 states. [2022-04-08 07:25:44,299 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:25:44,300 INFO L93 Difference]: Finished difference Result 63 states and 77 transitions. [2022-04-08 07:25:44,300 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 77 transitions. [2022-04-08 07:25:44,300 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:25:44,300 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:25:44,300 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 07:25:44,300 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 07:25:44,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 43 states have (on average 1.3255813953488371) internal successors, (57), 45 states have internal predecessors, (57), 11 states have call successors, (11), 8 states have call predecessors, (11), 6 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-08 07:25:44,305 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 76 transitions. [2022-04-08 07:25:44,306 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 76 transitions. Word has length 27 [2022-04-08 07:25:44,306 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 07:25:44,306 INFO L478 AbstractCegarLoop]: Abstraction has 61 states and 76 transitions. [2022-04-08 07:25:44,307 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 4 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-08 07:25:44,307 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 61 states and 76 transitions. [2022-04-08 07:25:46,391 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 76 edges. 75 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-08 07:25:46,392 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 76 transitions. [2022-04-08 07:25:46,392 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-04-08 07:25:46,392 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 07:25:46,393 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 07:25:46,415 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-08 07:25:46,599 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-08 07:25:46,599 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 07:25:46,600 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 07:25:46,600 INFO L85 PathProgramCache]: Analyzing trace with hash 1799714694, now seen corresponding path program 1 times [2022-04-08 07:25:46,600 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 07:25:46,600 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1156147013] [2022-04-08 07:25:52,680 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 4 AssignedVariables, -1 ReadonlyVariables, Eigenvalues: {}, 0 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-08 07:25:52,680 WARN L91 AcceleratorJordan]: Jordan acceleration failed, because NONLINEAR_UPDATE [2022-04-08 07:25:52,680 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 07:25:52,680 INFO L85 PathProgramCache]: Analyzing trace with hash 1799714694, now seen corresponding path program 2 times [2022-04-08 07:25:52,680 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 07:25:52,681 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1644782857] [2022-04-08 07:25:52,681 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 07:25:52,681 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 07:25:52,695 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 07:25:52,695 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1174615465] [2022-04-08 07:25:52,695 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 07:25:52,695 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 07:25:52,695 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 07:25:52,703 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-08 07:25:52,711 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-08 07:25:52,751 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 07:25:52,751 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 07:25:52,752 INFO L263 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 28 conjunts are in the unsatisfiable core [2022-04-08 07:25:52,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 07:25:52,767 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 07:25:53,228 INFO L272 TraceCheckUtils]: 0: Hoare triple {1825#true} call ULTIMATE.init(); {1825#true} is VALID [2022-04-08 07:25:53,228 INFO L290 TraceCheckUtils]: 1: Hoare triple {1825#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1825#true} is VALID [2022-04-08 07:25:53,228 INFO L290 TraceCheckUtils]: 2: Hoare triple {1825#true} assume true; {1825#true} is VALID [2022-04-08 07:25:53,229 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1825#true} {1825#true} #77#return; {1825#true} is VALID [2022-04-08 07:25:53,229 INFO L272 TraceCheckUtils]: 4: Hoare triple {1825#true} call #t~ret7 := main(); {1825#true} is VALID [2022-04-08 07:25:53,229 INFO L290 TraceCheckUtils]: 5: Hoare triple {1825#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {1825#true} is VALID [2022-04-08 07:25:53,229 INFO L272 TraceCheckUtils]: 6: Hoare triple {1825#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1825#true} is VALID [2022-04-08 07:25:53,229 INFO L290 TraceCheckUtils]: 7: Hoare triple {1825#true} ~cond := #in~cond; {1825#true} is VALID [2022-04-08 07:25:53,229 INFO L290 TraceCheckUtils]: 8: Hoare triple {1825#true} assume !(0 == ~cond); {1825#true} is VALID [2022-04-08 07:25:53,229 INFO L290 TraceCheckUtils]: 9: Hoare triple {1825#true} assume true; {1825#true} is VALID [2022-04-08 07:25:53,230 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1825#true} {1825#true} #69#return; {1825#true} is VALID [2022-04-08 07:25:53,230 INFO L290 TraceCheckUtils]: 11: Hoare triple {1825#true} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {1863#(and (= main_~b~0 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-08 07:25:53,231 INFO L290 TraceCheckUtils]: 12: Hoare triple {1863#(and (= main_~b~0 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1863#(and (= main_~b~0 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-08 07:25:53,231 INFO L290 TraceCheckUtils]: 13: Hoare triple {1863#(and (= main_~b~0 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} assume !!(#t~post6 < 20);havoc #t~post6; {1863#(and (= main_~b~0 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-08 07:25:53,231 INFO L272 TraceCheckUtils]: 14: Hoare triple {1863#(and (= main_~b~0 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {1825#true} is VALID [2022-04-08 07:25:53,232 INFO L290 TraceCheckUtils]: 15: Hoare triple {1825#true} ~cond := #in~cond; {1876#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-08 07:25:53,232 INFO L290 TraceCheckUtils]: 16: Hoare triple {1876#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {1880#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 07:25:53,233 INFO L290 TraceCheckUtils]: 17: Hoare triple {1880#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1880#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 07:25:53,234 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {1880#(not (= |__VERIFIER_assert_#in~cond| 0))} {1863#(and (= main_~b~0 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} #71#return; {1887#(and (= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0)) (= main_~b~0 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-08 07:25:53,234 INFO L290 TraceCheckUtils]: 19: Hoare triple {1887#(and (= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0)) (= main_~b~0 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} assume !!(0 != ~a~0 && 0 != ~b~0); {1887#(and (= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0)) (= main_~b~0 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-08 07:25:53,236 INFO L290 TraceCheckUtils]: 20: Hoare triple {1887#(and (= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0)) (= main_~b~0 main_~y~0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} assume 0 == (if ~a~0 < 0 && 0 != ~a~0 % 2 then ~a~0 % 2 - 2 else ~a~0 % 2) && 0 == (if ~b~0 < 0 && 0 != ~b~0 % 2 then ~b~0 % 2 - 2 else ~b~0 % 2);~a~0 := (if ~a~0 < 0 && 0 != ~a~0 % 2 then 1 + ~a~0 / 2 else ~a~0 / 2);~b~0 := (if ~b~0 < 0 && 0 != ~b~0 % 2 then 1 + ~b~0 / 2 else ~b~0 / 2);~p~0 := 4 * ~p~0; {1894#(and (= (+ main_~q~0 (* main_~y~0 main_~x~0 1)) (* main_~y~0 main_~x~0)) (= (div main_~y~0 2) main_~b~0) (= (mod main_~y~0 2) 0) (= main_~p~0 4) (= (div main_~x~0 2) main_~a~0) (= (mod main_~x~0 2) 0))} is VALID [2022-04-08 07:25:53,236 INFO L290 TraceCheckUtils]: 21: Hoare triple {1894#(and (= (+ main_~q~0 (* main_~y~0 main_~x~0 1)) (* main_~y~0 main_~x~0)) (= (div main_~y~0 2) main_~b~0) (= (mod main_~y~0 2) 0) (= main_~p~0 4) (= (div main_~x~0 2) main_~a~0) (= (mod main_~x~0 2) 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1894#(and (= (+ main_~q~0 (* main_~y~0 main_~x~0 1)) (* main_~y~0 main_~x~0)) (= (div main_~y~0 2) main_~b~0) (= (mod main_~y~0 2) 0) (= main_~p~0 4) (= (div main_~x~0 2) main_~a~0) (= (mod main_~x~0 2) 0))} is VALID [2022-04-08 07:25:53,237 INFO L290 TraceCheckUtils]: 22: Hoare triple {1894#(and (= (+ main_~q~0 (* main_~y~0 main_~x~0 1)) (* main_~y~0 main_~x~0)) (= (div main_~y~0 2) main_~b~0) (= (mod main_~y~0 2) 0) (= main_~p~0 4) (= (div main_~x~0 2) main_~a~0) (= (mod main_~x~0 2) 0))} assume !!(#t~post6 < 20);havoc #t~post6; {1894#(and (= (+ main_~q~0 (* main_~y~0 main_~x~0 1)) (* main_~y~0 main_~x~0)) (= (div main_~y~0 2) main_~b~0) (= (mod main_~y~0 2) 0) (= main_~p~0 4) (= (div main_~x~0 2) main_~a~0) (= (mod main_~x~0 2) 0))} is VALID [2022-04-08 07:25:53,241 INFO L272 TraceCheckUtils]: 23: Hoare triple {1894#(and (= (+ main_~q~0 (* main_~y~0 main_~x~0 1)) (* main_~y~0 main_~x~0)) (= (div main_~y~0 2) main_~b~0) (= (mod main_~y~0 2) 0) (= main_~p~0 4) (= (div main_~x~0 2) main_~a~0) (= (mod main_~x~0 2) 0))} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {1904#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 07:25:53,241 INFO L290 TraceCheckUtils]: 24: Hoare triple {1904#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1908#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 07:25:53,242 INFO L290 TraceCheckUtils]: 25: Hoare triple {1908#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1826#false} is VALID [2022-04-08 07:25:53,242 INFO L290 TraceCheckUtils]: 26: Hoare triple {1826#false} assume !false; {1826#false} is VALID [2022-04-08 07:25:53,242 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 07:25:53,242 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-08 07:26:49,865 INFO L290 TraceCheckUtils]: 26: Hoare triple {1826#false} assume !false; {1826#false} is VALID [2022-04-08 07:26:49,866 INFO L290 TraceCheckUtils]: 25: Hoare triple {1908#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1826#false} is VALID [2022-04-08 07:26:49,866 INFO L290 TraceCheckUtils]: 24: Hoare triple {1904#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1908#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 07:26:49,867 INFO L272 TraceCheckUtils]: 23: Hoare triple {1924#(= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {1904#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 07:26:49,868 INFO L290 TraceCheckUtils]: 22: Hoare triple {1924#(= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))} assume !!(#t~post6 < 20);havoc #t~post6; {1924#(= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))} is VALID [2022-04-08 07:26:49,868 INFO L290 TraceCheckUtils]: 21: Hoare triple {1924#(= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1924#(= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))} is VALID [2022-04-08 07:26:49,873 INFO L290 TraceCheckUtils]: 20: Hoare triple {1934#(or (not (= (mod main_~b~0 2) 0)) (= (+ (* (div main_~b~0 2) (* main_~p~0 4) (div main_~a~0 2)) main_~q~0) (* main_~y~0 main_~x~0)) (not (= (mod main_~a~0 2) 0)))} assume 0 == (if ~a~0 < 0 && 0 != ~a~0 % 2 then ~a~0 % 2 - 2 else ~a~0 % 2) && 0 == (if ~b~0 < 0 && 0 != ~b~0 % 2 then ~b~0 % 2 - 2 else ~b~0 % 2);~a~0 := (if ~a~0 < 0 && 0 != ~a~0 % 2 then 1 + ~a~0 / 2 else ~a~0 / 2);~b~0 := (if ~b~0 < 0 && 0 != ~b~0 % 2 then 1 + ~b~0 / 2 else ~b~0 / 2);~p~0 := 4 * ~p~0; {1924#(= (+ main_~q~0 (* main_~b~0 main_~a~0 main_~p~0)) (* main_~y~0 main_~x~0))} is VALID [2022-04-08 07:26:49,874 INFO L290 TraceCheckUtils]: 19: Hoare triple {1934#(or (not (= (mod main_~b~0 2) 0)) (= (+ (* (div main_~b~0 2) (* main_~p~0 4) (div main_~a~0 2)) main_~q~0) (* main_~y~0 main_~x~0)) (not (= (mod main_~a~0 2) 0)))} assume !!(0 != ~a~0 && 0 != ~b~0); {1934#(or (not (= (mod main_~b~0 2) 0)) (= (+ (* (div main_~b~0 2) (* main_~p~0 4) (div main_~a~0 2)) main_~q~0) (* main_~y~0 main_~x~0)) (not (= (mod main_~a~0 2) 0)))} is VALID [2022-04-08 07:26:49,880 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {1880#(not (= |__VERIFIER_assert_#in~cond| 0))} {1825#true} #71#return; {1934#(or (not (= (mod main_~b~0 2) 0)) (= (+ (* (div main_~b~0 2) (* main_~p~0 4) (div main_~a~0 2)) main_~q~0) (* main_~y~0 main_~x~0)) (not (= (mod main_~a~0 2) 0)))} is VALID [2022-04-08 07:26:49,880 INFO L290 TraceCheckUtils]: 17: Hoare triple {1880#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1880#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 07:26:49,884 INFO L290 TraceCheckUtils]: 16: Hoare triple {1950#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {1880#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 07:26:49,885 INFO L290 TraceCheckUtils]: 15: Hoare triple {1825#true} ~cond := #in~cond; {1950#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 07:26:49,885 INFO L272 TraceCheckUtils]: 14: Hoare triple {1825#true} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {1825#true} is VALID [2022-04-08 07:26:49,885 INFO L290 TraceCheckUtils]: 13: Hoare triple {1825#true} assume !!(#t~post6 < 20);havoc #t~post6; {1825#true} is VALID [2022-04-08 07:26:49,885 INFO L290 TraceCheckUtils]: 12: Hoare triple {1825#true} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1825#true} is VALID [2022-04-08 07:26:49,885 INFO L290 TraceCheckUtils]: 11: Hoare triple {1825#true} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {1825#true} is VALID [2022-04-08 07:26:49,885 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1825#true} {1825#true} #69#return; {1825#true} is VALID [2022-04-08 07:26:49,885 INFO L290 TraceCheckUtils]: 9: Hoare triple {1825#true} assume true; {1825#true} is VALID [2022-04-08 07:26:49,885 INFO L290 TraceCheckUtils]: 8: Hoare triple {1825#true} assume !(0 == ~cond); {1825#true} is VALID [2022-04-08 07:26:49,885 INFO L290 TraceCheckUtils]: 7: Hoare triple {1825#true} ~cond := #in~cond; {1825#true} is VALID [2022-04-08 07:26:49,885 INFO L272 TraceCheckUtils]: 6: Hoare triple {1825#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1825#true} is VALID [2022-04-08 07:26:49,886 INFO L290 TraceCheckUtils]: 5: Hoare triple {1825#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {1825#true} is VALID [2022-04-08 07:26:49,886 INFO L272 TraceCheckUtils]: 4: Hoare triple {1825#true} call #t~ret7 := main(); {1825#true} is VALID [2022-04-08 07:26:49,886 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1825#true} {1825#true} #77#return; {1825#true} is VALID [2022-04-08 07:26:49,886 INFO L290 TraceCheckUtils]: 2: Hoare triple {1825#true} assume true; {1825#true} is VALID [2022-04-08 07:26:49,886 INFO L290 TraceCheckUtils]: 1: Hoare triple {1825#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1825#true} is VALID [2022-04-08 07:26:49,886 INFO L272 TraceCheckUtils]: 0: Hoare triple {1825#true} call ULTIMATE.init(); {1825#true} is VALID [2022-04-08 07:26:49,886 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 07:26:49,886 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 07:26:49,887 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1644782857] [2022-04-08 07:26:49,887 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 07:26:49,887 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1174615465] [2022-04-08 07:26:49,887 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1174615465] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-08 07:26:49,887 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-08 07:26:49,887 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-04-08 07:26:49,887 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 07:26:49,887 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1156147013] [2022-04-08 07:26:49,888 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1156147013] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 07:26:49,888 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 07:26:49,888 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-08 07:26:49,888 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [712369818] [2022-04-08 07:26:49,888 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 07:26:49,888 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 27 [2022-04-08 07:26:49,889 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 07:26:49,889 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 9 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 07:26:49,923 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 27 edges. 27 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:26:49,923 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-08 07:26:49,923 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 07:26:49,924 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-08 07:26:49,924 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2022-04-08 07:26:49,924 INFO L87 Difference]: Start difference. First operand 61 states and 76 transitions. Second operand has 9 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 07:26:50,616 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:26:50,616 INFO L93 Difference]: Finished difference Result 76 states and 96 transitions. [2022-04-08 07:26:50,617 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-08 07:26:50,617 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 27 [2022-04-08 07:26:50,617 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 07:26:50,617 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 07:26:50,618 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 68 transitions. [2022-04-08 07:26:50,619 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 07:26:50,620 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 68 transitions. [2022-04-08 07:26:50,620 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 68 transitions. [2022-04-08 07:26:50,696 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 68 edges. 68 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:26:50,698 INFO L225 Difference]: With dead ends: 76 [2022-04-08 07:26:50,698 INFO L226 Difference]: Without dead ends: 74 [2022-04-08 07:26:50,698 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 42 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=44, Invalid=138, Unknown=0, NotChecked=0, Total=182 [2022-04-08 07:26:50,699 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 24 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 197 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 202 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 197 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-08 07:26:50,699 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 126 Invalid, 202 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 197 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-08 07:26:50,700 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2022-04-08 07:26:50,773 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 68. [2022-04-08 07:26:50,773 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 07:26:50,773 INFO L82 GeneralOperation]: Start isEquivalent. First operand 74 states. Second operand has 68 states, 48 states have (on average 1.2916666666666667) internal successors, (62), 51 states have internal predecessors, (62), 12 states have call successors, (12), 9 states have call predecessors, (12), 7 states have return successors, (9), 7 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 07:26:50,773 INFO L74 IsIncluded]: Start isIncluded. First operand 74 states. Second operand has 68 states, 48 states have (on average 1.2916666666666667) internal successors, (62), 51 states have internal predecessors, (62), 12 states have call successors, (12), 9 states have call predecessors, (12), 7 states have return successors, (9), 7 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 07:26:50,774 INFO L87 Difference]: Start difference. First operand 74 states. Second operand has 68 states, 48 states have (on average 1.2916666666666667) internal successors, (62), 51 states have internal predecessors, (62), 12 states have call successors, (12), 9 states have call predecessors, (12), 7 states have return successors, (9), 7 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 07:26:50,782 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:26:50,782 INFO L93 Difference]: Finished difference Result 74 states and 94 transitions. [2022-04-08 07:26:50,782 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 94 transitions. [2022-04-08 07:26:50,782 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:26:50,782 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:26:50,784 INFO L74 IsIncluded]: Start isIncluded. First operand has 68 states, 48 states have (on average 1.2916666666666667) internal successors, (62), 51 states have internal predecessors, (62), 12 states have call successors, (12), 9 states have call predecessors, (12), 7 states have return successors, (9), 7 states have call predecessors, (9), 9 states have call successors, (9) Second operand 74 states. [2022-04-08 07:26:50,784 INFO L87 Difference]: Start difference. First operand has 68 states, 48 states have (on average 1.2916666666666667) internal successors, (62), 51 states have internal predecessors, (62), 12 states have call successors, (12), 9 states have call predecessors, (12), 7 states have return successors, (9), 7 states have call predecessors, (9), 9 states have call successors, (9) Second operand 74 states. [2022-04-08 07:26:50,789 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:26:50,789 INFO L93 Difference]: Finished difference Result 74 states and 94 transitions. [2022-04-08 07:26:50,789 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 94 transitions. [2022-04-08 07:26:50,789 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:26:50,789 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:26:50,789 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 07:26:50,789 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 07:26:50,790 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 48 states have (on average 1.2916666666666667) internal successors, (62), 51 states have internal predecessors, (62), 12 states have call successors, (12), 9 states have call predecessors, (12), 7 states have return successors, (9), 7 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 07:26:50,792 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 83 transitions. [2022-04-08 07:26:50,792 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 83 transitions. Word has length 27 [2022-04-08 07:26:50,793 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 07:26:50,793 INFO L478 AbstractCegarLoop]: Abstraction has 68 states and 83 transitions. [2022-04-08 07:26:50,793 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 07:26:50,793 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 68 states and 83 transitions. [2022-04-08 07:26:52,887 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 83 edges. 82 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-08 07:26:52,888 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 83 transitions. [2022-04-08 07:26:52,888 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-04-08 07:26:52,888 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 07:26:52,888 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 07:26:52,904 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-08 07:26:53,091 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-08 07:26:53,092 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 07:26:53,092 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 07:26:53,092 INFO L85 PathProgramCache]: Analyzing trace with hash -1613968938, now seen corresponding path program 1 times [2022-04-08 07:26:53,092 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 07:26:53,092 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [387976862] [2022-04-08 07:26:53,093 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 07:26:53,093 INFO L85 PathProgramCache]: Analyzing trace with hash -1613968938, now seen corresponding path program 2 times [2022-04-08 07:26:53,093 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 07:26:53,093 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [53764168] [2022-04-08 07:26:53,093 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 07:26:53,093 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 07:26:53,107 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 07:26:53,107 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [645663907] [2022-04-08 07:26:53,107 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 07:26:53,107 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 07:26:53,108 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 07:26:53,108 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-08 07:26:53,113 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-08 07:26:53,151 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 07:26:53,151 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 07:26:53,152 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 10 conjunts are in the unsatisfiable core [2022-04-08 07:26:53,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 07:26:53,161 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 07:26:53,331 INFO L272 TraceCheckUtils]: 0: Hoare triple {2438#true} call ULTIMATE.init(); {2438#true} is VALID [2022-04-08 07:26:53,331 INFO L290 TraceCheckUtils]: 1: Hoare triple {2438#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2438#true} is VALID [2022-04-08 07:26:53,331 INFO L290 TraceCheckUtils]: 2: Hoare triple {2438#true} assume true; {2438#true} is VALID [2022-04-08 07:26:53,331 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2438#true} {2438#true} #77#return; {2438#true} is VALID [2022-04-08 07:26:53,331 INFO L272 TraceCheckUtils]: 4: Hoare triple {2438#true} call #t~ret7 := main(); {2438#true} is VALID [2022-04-08 07:26:53,331 INFO L290 TraceCheckUtils]: 5: Hoare triple {2438#true} havoc ~x~0;havoc ~y~0;havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {2438#true} is VALID [2022-04-08 07:26:53,331 INFO L272 TraceCheckUtils]: 6: Hoare triple {2438#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {2438#true} is VALID [2022-04-08 07:26:53,332 INFO L290 TraceCheckUtils]: 7: Hoare triple {2438#true} ~cond := #in~cond; {2464#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-08 07:26:53,332 INFO L290 TraceCheckUtils]: 8: Hoare triple {2464#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {2468#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-08 07:26:53,332 INFO L290 TraceCheckUtils]: 9: Hoare triple {2468#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {2468#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-08 07:26:53,333 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2468#(not (= |assume_abort_if_not_#in~cond| 0))} {2438#true} #69#return; {2475#(<= 1 main_~y~0)} is VALID [2022-04-08 07:26:53,333 INFO L290 TraceCheckUtils]: 11: Hoare triple {2475#(<= 1 main_~y~0)} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0; {2479#(<= 1 main_~b~0)} is VALID [2022-04-08 07:26:53,334 INFO L290 TraceCheckUtils]: 12: Hoare triple {2479#(<= 1 main_~b~0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {2479#(<= 1 main_~b~0)} is VALID [2022-04-08 07:26:53,334 INFO L290 TraceCheckUtils]: 13: Hoare triple {2479#(<= 1 main_~b~0)} assume !!(#t~post6 < 20);havoc #t~post6; {2479#(<= 1 main_~b~0)} is VALID [2022-04-08 07:26:53,334 INFO L272 TraceCheckUtils]: 14: Hoare triple {2479#(<= 1 main_~b~0)} call __VERIFIER_assert((if ~q~0 + ~a~0 * ~b~0 * ~p~0 == ~x~0 * ~y~0 then 1 else 0)); {2438#true} is VALID [2022-04-08 07:26:53,334 INFO L290 TraceCheckUtils]: 15: Hoare triple {2438#true} ~cond := #in~cond; {2438#true} is VALID [2022-04-08 07:26:53,334 INFO L290 TraceCheckUtils]: 16: Hoare triple {2438#true} assume !(0 == ~cond); {2438#true} is VALID [2022-04-08 07:26:53,334 INFO L290 TraceCheckUtils]: 17: Hoare triple {2438#true} assume true; {2438#true} is VALID [2022-04-08 07:26:53,335 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {2438#true} {2479#(<= 1 main_~b~0)} #71#return; {2479#(<= 1 main_~b~0)} is VALID [2022-04-08 07:26:53,336 INFO L290 TraceCheckUtils]: 19: Hoare triple {2479#(<= 1 main_~b~0)} assume !(0 != ~a~0 && 0 != ~b~0); {2504#(and (= main_~a~0 0) (<= 1 main_~b~0))} is VALID [2022-04-08 07:26:53,336 INFO L272 TraceCheckUtils]: 20: Hoare triple {2504#(and (= main_~a~0 0) (<= 1 main_~b~0))} call __VERIFIER_assert((if ~q~0 == ~x~0 * ~y~0 then 1 else 0)); {2438#true} is VALID [2022-04-08 07:26:53,336 INFO L290 TraceCheckUtils]: 21: Hoare triple {2438#true} ~cond := #in~cond; {2438#true} is VALID [2022-04-08 07:26:53,336 INFO L290 TraceCheckUtils]: 22: Hoare triple {2438#true} assume !(0 == ~cond); {2438#true} is VALID [2022-04-08 07:26:53,352 INFO L290 TraceCheckUtils]: 23: Hoare triple {2438#true} assume true; {2438#true} is VALID [2022-04-08 07:26:53,355 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {2438#true} {2504#(and (= main_~a~0 0) (<= 1 main_~b~0))} #73#return; {2504#(and (= main_~a~0 0) (<= 1 main_~b~0))} is VALID [2022-04-08 07:26:53,356 INFO L272 TraceCheckUtils]: 25: Hoare triple {2504#(and (= main_~a~0 0) (<= 1 main_~b~0))} call __VERIFIER_assert((if 0 == ~a~0 * ~b~0 then 1 else 0)); {2523#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 07:26:53,358 INFO L290 TraceCheckUtils]: 26: Hoare triple {2523#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {2527#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 07:26:53,358 INFO L290 TraceCheckUtils]: 27: Hoare triple {2527#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {2439#false} is VALID [2022-04-08 07:26:53,358 INFO L290 TraceCheckUtils]: 28: Hoare triple {2439#false} assume !false; {2439#false} is VALID [2022-04-08 07:26:53,359 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-08 07:26:53,359 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 07:26:53,359 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 07:26:53,359 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [53764168] [2022-04-08 07:26:53,359 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 07:26:53,359 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [645663907] [2022-04-08 07:26:53,359 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [645663907] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 07:26:53,359 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 07:26:53,359 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-08 07:26:53,359 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 07:26:53,360 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [387976862] [2022-04-08 07:26:53,360 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [387976862] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 07:26:53,360 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 07:26:53,360 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-08 07:26:53,360 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2075858568] [2022-04-08 07:26:53,360 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 07:26:53,360 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 29 [2022-04-08 07:26:53,361 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 07:26:53,361 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-08 07:26:53,383 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 26 edges. 26 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:26:53,383 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-08 07:26:53,383 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 07:26:53,384 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-08 07:26:53,384 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2022-04-08 07:26:53,384 INFO L87 Difference]: Start difference. First operand 68 states and 83 transitions. Second operand has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-08 07:26:53,839 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:26:53,840 INFO L93 Difference]: Finished difference Result 85 states and 107 transitions. [2022-04-08 07:26:53,840 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-08 07:26:53,840 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 29 [2022-04-08 07:26:53,840 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 07:26:53,840 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-08 07:26:53,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 57 transitions. [2022-04-08 07:26:53,842 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-08 07:26:53,843 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 57 transitions. [2022-04-08 07:26:53,843 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 9 states and 57 transitions. [2022-04-08 07:26:53,888 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 57 edges. 57 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 07:26:53,889 INFO L225 Difference]: With dead ends: 85 [2022-04-08 07:26:53,889 INFO L226 Difference]: Without dead ends: 65 [2022-04-08 07:26:53,890 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2022-04-08 07:26:53,890 INFO L913 BasicCegarLoop]: 26 mSDtfsCounter, 33 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 122 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 131 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 122 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-08 07:26:53,891 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 157 Invalid, 131 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 122 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-08 07:26:53,891 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2022-04-08 07:26:53,966 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 62. [2022-04-08 07:26:53,967 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 07:26:53,967 INFO L82 GeneralOperation]: Start isEquivalent. First operand 65 states. Second operand has 62 states, 45 states have (on average 1.3555555555555556) internal successors, (61), 48 states have internal predecessors, (61), 11 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-08 07:26:53,967 INFO L74 IsIncluded]: Start isIncluded. First operand 65 states. Second operand has 62 states, 45 states have (on average 1.3555555555555556) internal successors, (61), 48 states have internal predecessors, (61), 11 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-08 07:26:53,968 INFO L87 Difference]: Start difference. First operand 65 states. Second operand has 62 states, 45 states have (on average 1.3555555555555556) internal successors, (61), 48 states have internal predecessors, (61), 11 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-08 07:26:53,970 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:26:53,970 INFO L93 Difference]: Finished difference Result 65 states and 85 transitions. [2022-04-08 07:26:53,970 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 85 transitions. [2022-04-08 07:26:53,971 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:26:53,971 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:26:53,971 INFO L74 IsIncluded]: Start isIncluded. First operand has 62 states, 45 states have (on average 1.3555555555555556) internal successors, (61), 48 states have internal predecessors, (61), 11 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) Second operand 65 states. [2022-04-08 07:26:53,971 INFO L87 Difference]: Start difference. First operand has 62 states, 45 states have (on average 1.3555555555555556) internal successors, (61), 48 states have internal predecessors, (61), 11 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) Second operand 65 states. [2022-04-08 07:26:53,973 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 07:26:53,973 INFO L93 Difference]: Finished difference Result 65 states and 85 transitions. [2022-04-08 07:26:53,973 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 85 transitions. [2022-04-08 07:26:53,974 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 07:26:53,974 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 07:26:53,974 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 07:26:53,974 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 07:26:53,974 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 45 states have (on average 1.3555555555555556) internal successors, (61), 48 states have internal predecessors, (61), 11 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-08 07:26:53,976 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 80 transitions. [2022-04-08 07:26:53,976 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 80 transitions. Word has length 29 [2022-04-08 07:26:53,977 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 07:26:53,977 INFO L478 AbstractCegarLoop]: Abstraction has 62 states and 80 transitions. [2022-04-08 07:26:53,977 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-08 07:26:53,977 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 62 states and 80 transitions. [2022-04-08 07:26:56,080 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 80 edges. 79 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-08 07:26:56,080 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 80 transitions. [2022-04-08 07:26:56,081 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-08 07:26:56,081 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 07:26:56,081 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 07:26:56,097 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2022-04-08 07:26:56,283 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-08 07:26:56,283 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 07:26:56,284 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 07:26:56,284 INFO L85 PathProgramCache]: Analyzing trace with hash -1357155568, now seen corresponding path program 1 times [2022-04-08 07:26:56,284 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 07:26:56,284 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1057931483] [2022-04-08 07:27:03,780 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 1 HavocedVariables, 3 AssignedVariables, 1 ReadonlyVariables, Eigenvalues: {1={1=1, 2=2}}, 1 SequentialAcceleration, 0 AlternatingAcceleration, 1 QuantifierFreeResult [2022-04-08 07:27:03,782 FATAL L? ?]: The Plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction has thrown an exception: java.lang.AssertionError: free variables [|v_main_#t~post6_17|] at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.cfg.transitions.UnmodifiableTransFormula.(UnmodifiableTransFormula.java:97) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.cfg.transitions.TransFormulaBuilder.finishConstruction(TransFormulaBuilder.java:324) at de.uni_freiburg.informatik.ultimate.lib.acceleratedinterpolation.PredicateHelper.normalizeTerm(PredicateHelper.java:201) at de.uni_freiburg.informatik.ultimate.lib.acceleratedinterpolation.AcceleratedInterpolationCore.acceleratedInterpolationCoreIsCorrect(AcceleratedInterpolationCore.java:254) at de.uni_freiburg.informatik.ultimate.lib.acceleratedinterpolation.AcceleratedInterpolation.(AcceleratedInterpolation.java:190) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleAcceleratedInterpolation.construct(IpTcStrategyModuleAcceleratedInterpolation.java:80) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.isCorrect(IpTcStrategyModuleBase.java:57) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.checkFeasibility(AutomatonFreeRefinementEngine.java:209) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:121) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:595) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:414) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:349) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:331) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.CegarLoopUtils.getCegarLoopResult(CegarLoopUtils.java:56) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:412) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:262) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:175) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:154) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:123) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:320) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2022-04-08 07:27:03,785 INFO L158 Benchmark]: Toolchain (without parser) took 123622.17ms. Allocated memory was 192.9MB in the beginning and 238.0MB in the end (delta: 45.1MB). Free memory was 144.0MB in the beginning and 210.9MB in the end (delta: -66.9MB). Peak memory consumption was 110.9MB. Max. memory is 8.0GB. [2022-04-08 07:27:03,785 INFO L158 Benchmark]: CDTParser took 0.11ms. Allocated memory is still 192.9MB. Free memory is still 160.4MB. There was no memory consumed. Max. memory is 8.0GB. [2022-04-08 07:27:03,786 INFO L158 Benchmark]: CACSL2BoogieTranslator took 235.37ms. Allocated memory was 192.9MB in the beginning and 238.0MB in the end (delta: 45.1MB). Free memory was 143.8MB in the beginning and 213.6MB in the end (delta: -69.9MB). Peak memory consumption was 10.3MB. Max. memory is 8.0GB. [2022-04-08 07:27:03,786 INFO L158 Benchmark]: Boogie Preprocessor took 43.15ms. Allocated memory is still 238.0MB. Free memory was 213.6MB in the beginning and 212.1MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-04-08 07:27:03,786 INFO L158 Benchmark]: RCFGBuilder took 340.90ms. Allocated memory is still 238.0MB. Free memory was 212.1MB in the beginning and 198.4MB in the end (delta: 13.6MB). Peak memory consumption was 13.6MB. Max. memory is 8.0GB. [2022-04-08 07:27:03,786 INFO L158 Benchmark]: TraceAbstraction took 122996.88ms. Allocated memory is still 238.0MB. Free memory was 198.0MB in the beginning and 210.9MB in the end (delta: -12.9MB). Peak memory consumption was 120.6MB. Max. memory is 8.0GB. [2022-04-08 07:27:03,787 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.11ms. Allocated memory is still 192.9MB. Free memory is still 160.4MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 235.37ms. Allocated memory was 192.9MB in the beginning and 238.0MB in the end (delta: 45.1MB). Free memory was 143.8MB in the beginning and 213.6MB in the end (delta: -69.9MB). Peak memory consumption was 10.3MB. Max. memory is 8.0GB. * Boogie Preprocessor took 43.15ms. Allocated memory is still 238.0MB. Free memory was 213.6MB in the beginning and 212.1MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 340.90ms. Allocated memory is still 238.0MB. Free memory was 212.1MB in the beginning and 198.4MB in the end (delta: 13.6MB). Peak memory consumption was 13.6MB. Max. memory is 8.0GB. * TraceAbstraction took 122996.88ms. Allocated memory is still 238.0MB. Free memory was 198.0MB in the beginning and 210.9MB in the end (delta: -12.9MB). Peak memory consumption was 120.6MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - ExceptionOrErrorResult: AssertionError: free variables [|v_main_#t~post6_17|] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: AssertionError: free variables [|v_main_#t~post6_17|]: de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.cfg.transitions.UnmodifiableTransFormula.(UnmodifiableTransFormula.java:97) RESULT: Ultimate could not prove your program: Toolchain returned no result. [2022-04-08 07:27:03,811 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...