/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/cohendiv-ll_unwindbound1.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-e106359-m [2022-04-15 07:47:43,535 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-15 07:47:43,537 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-15 07:47:43,581 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-15 07:47:43,581 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-15 07:47:43,582 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-15 07:47:43,584 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-15 07:47:43,586 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-15 07:47:43,587 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-15 07:47:43,590 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-15 07:47:43,591 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-15 07:47:43,592 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-15 07:47:43,592 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-15 07:47:43,593 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-15 07:47:43,594 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-15 07:47:43,596 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-15 07:47:43,597 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-15 07:47:43,597 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-15 07:47:43,599 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-15 07:47:43,602 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-15 07:47:43,604 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-15 07:47:43,604 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-15 07:47:43,605 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-15 07:47:43,605 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-15 07:47:43,607 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-15 07:47:43,611 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-15 07:47:43,611 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-15 07:47:43,611 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-15 07:47:43,612 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-15 07:47:43,612 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-15 07:47:43,613 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-15 07:47:43,613 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-15 07:47:43,614 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-15 07:47:43,615 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-15 07:47:43,615 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-15 07:47:43,616 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-15 07:47:43,616 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-15 07:47:43,616 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-15 07:47:43,616 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-15 07:47:43,617 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-15 07:47:43,617 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-15 07:47:43,618 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-15 07:47:43,619 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-04-15 07:47:43,627 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-15 07:47:43,627 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-15 07:47:43,628 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-15 07:47:43,628 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-15 07:47:43,628 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-15 07:47:43,628 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-15 07:47:43,628 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-15 07:47:43,628 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-15 07:47:43,628 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-15 07:47:43,629 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-15 07:47:43,629 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-15 07:47:43,629 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-15 07:47:43,629 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-15 07:47:43,629 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-15 07:47:43,629 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-15 07:47:43,630 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-15 07:47:43,630 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-15 07:47:43,630 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-15 07:47:43,630 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 07:47:43,630 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-15 07:47:43,630 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-15 07:47:43,630 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-15 07:47:43,630 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-15 07:47:43,630 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-15 07:47:43,630 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-15 07:47:43,630 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-15 07:47:43,822 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-15 07:47:43,836 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-15 07:47:43,838 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-15 07:47:43,838 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-15 07:47:43,839 INFO L275 PluginConnector]: CDTParser initialized [2022-04-15 07:47:43,839 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/cohendiv-ll_unwindbound1.c [2022-04-15 07:47:43,893 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7bd9589bd/32f826f947704a438736913edc736185/FLAGd575c36ce [2022-04-15 07:47:44,233 INFO L306 CDTParser]: Found 1 translation units. [2022-04-15 07:47:44,233 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohendiv-ll_unwindbound1.c [2022-04-15 07:47:44,237 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7bd9589bd/32f826f947704a438736913edc736185/FLAGd575c36ce [2022-04-15 07:47:44,245 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7bd9589bd/32f826f947704a438736913edc736185 [2022-04-15 07:47:44,247 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-15 07:47:44,247 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-15 07:47:44,248 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-15 07:47:44,249 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-15 07:47:44,251 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-15 07:47:44,252 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 07:47:44" (1/1) ... [2022-04-15 07:47:44,253 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6df6da6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:47:44, skipping insertion in model container [2022-04-15 07:47:44,253 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 07:47:44" (1/1) ... [2022-04-15 07:47:44,257 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-15 07:47:44,268 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-15 07:47:44,415 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohendiv-ll_unwindbound1.c[576,589] [2022-04-15 07:47:44,438 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 07:47:44,448 INFO L203 MainTranslator]: Completed pre-run [2022-04-15 07:47:44,456 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohendiv-ll_unwindbound1.c[576,589] [2022-04-15 07:47:44,473 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 07:47:44,483 INFO L208 MainTranslator]: Completed translation [2022-04-15 07:47:44,483 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:47:44 WrapperNode [2022-04-15 07:47:44,484 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-15 07:47:44,484 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-15 07:47:44,485 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-15 07:47:44,485 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-15 07:47:44,491 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:47:44" (1/1) ... [2022-04-15 07:47:44,492 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:47:44" (1/1) ... [2022-04-15 07:47:44,497 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:47:44" (1/1) ... [2022-04-15 07:47:44,498 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:47:44" (1/1) ... [2022-04-15 07:47:44,509 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:47:44" (1/1) ... [2022-04-15 07:47:44,514 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:47:44" (1/1) ... [2022-04-15 07:47:44,518 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:47:44" (1/1) ... [2022-04-15 07:47:44,520 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-15 07:47:44,520 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-15 07:47:44,520 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-15 07:47:44,520 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-15 07:47:44,521 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:47:44" (1/1) ... [2022-04-15 07:47:44,526 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 07:47:44,533 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 07:47:44,543 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-15 07:47:44,561 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-15 07:47:44,579 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-15 07:47:44,579 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-15 07:47:44,580 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-15 07:47:44,580 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-15 07:47:44,580 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-15 07:47:44,580 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-15 07:47:44,580 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-15 07:47:44,580 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-15 07:47:44,580 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-15 07:47:44,580 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-15 07:47:44,581 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-15 07:47:44,581 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-15 07:47:44,582 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-15 07:47:44,582 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-15 07:47:44,582 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-15 07:47:44,582 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-15 07:47:44,582 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-15 07:47:44,582 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-15 07:47:44,582 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-15 07:47:44,582 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-15 07:47:44,631 INFO L234 CfgBuilder]: Building ICFG [2022-04-15 07:47:44,632 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-15 07:47:44,823 INFO L275 CfgBuilder]: Performing block encoding [2022-04-15 07:47:44,828 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-15 07:47:44,828 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-15 07:47:44,829 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 07:47:44 BoogieIcfgContainer [2022-04-15 07:47:44,829 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-15 07:47:44,831 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-15 07:47:44,831 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-15 07:47:44,846 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-15 07:47:44,846 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.04 07:47:44" (1/3) ... [2022-04-15 07:47:44,846 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6c2d01db and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 07:47:44, skipping insertion in model container [2022-04-15 07:47:44,846 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:47:44" (2/3) ... [2022-04-15 07:47:44,847 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6c2d01db and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 07:47:44, skipping insertion in model container [2022-04-15 07:47:44,847 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 07:47:44" (3/3) ... [2022-04-15 07:47:44,848 INFO L111 eAbstractionObserver]: Analyzing ICFG cohendiv-ll_unwindbound1.c [2022-04-15 07:47:44,851 INFO L202 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-15 07:47:44,851 INFO L161 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-15 07:47:44,906 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-15 07:47:44,910 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-15 07:47:44,910 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-15 07:47:44,931 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 22 states have (on average 1.4090909090909092) internal successors, (31), 23 states have internal predecessors, (31), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 07:47:44,935 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-15 07:47:44,935 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 07:47:44,936 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 07:47:44,937 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 07:47:44,943 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 07:47:44,944 INFO L85 PathProgramCache]: Analyzing trace with hash -1588022502, now seen corresponding path program 1 times [2022-04-15 07:47:44,949 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 07:47:44,951 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2054307977] [2022-04-15 07:47:44,959 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 07:47:44,959 INFO L85 PathProgramCache]: Analyzing trace with hash -1588022502, now seen corresponding path program 2 times [2022-04-15 07:47:44,962 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 07:47:44,963 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1009201955] [2022-04-15 07:47:44,963 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:47:44,964 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 07:47:45,059 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:47:45,117 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 07:47:45,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:47:45,147 INFO L290 TraceCheckUtils]: 0: Hoare triple {50#(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(14, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {41#true} is VALID [2022-04-15 07:47:45,147 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume true; {41#true} is VALID [2022-04-15 07:47:45,147 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {41#true} {41#true} #93#return; {41#true} is VALID [2022-04-15 07:47:45,148 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 07:47:45,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:47:45,164 INFO L290 TraceCheckUtils]: 0: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 07:47:45,165 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 07:47:45,165 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 07:47:45,165 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#false} {41#true} #77#return; {42#false} is VALID [2022-04-15 07:47:45,166 INFO L272 TraceCheckUtils]: 0: Hoare triple {41#true} call ULTIMATE.init(); {50#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 07:47:45,166 INFO L290 TraceCheckUtils]: 1: Hoare triple {50#(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(14, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {41#true} is VALID [2022-04-15 07:47:45,167 INFO L290 TraceCheckUtils]: 2: Hoare triple {41#true} assume true; {41#true} is VALID [2022-04-15 07:47:45,167 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {41#true} {41#true} #93#return; {41#true} is VALID [2022-04-15 07:47:45,167 INFO L272 TraceCheckUtils]: 4: Hoare triple {41#true} call #t~ret8 := main(); {41#true} is VALID [2022-04-15 07:47:45,167 INFO L290 TraceCheckUtils]: 5: Hoare triple {41#true} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {41#true} is VALID [2022-04-15 07:47:45,168 INFO L272 TraceCheckUtils]: 6: Hoare triple {41#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {41#true} is VALID [2022-04-15 07:47:45,168 INFO L290 TraceCheckUtils]: 7: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 07:47:45,168 INFO L290 TraceCheckUtils]: 8: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 07:47:45,168 INFO L290 TraceCheckUtils]: 9: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 07:47:45,169 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {42#false} {41#true} #77#return; {42#false} is VALID [2022-04-15 07:47:45,170 INFO L290 TraceCheckUtils]: 11: Hoare triple {42#false} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {42#false} is VALID [2022-04-15 07:47:45,170 INFO L290 TraceCheckUtils]: 12: Hoare triple {42#false} assume !true; {42#false} is VALID [2022-04-15 07:47:45,170 INFO L272 TraceCheckUtils]: 13: Hoare triple {42#false} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {42#false} is VALID [2022-04-15 07:47:45,170 INFO L290 TraceCheckUtils]: 14: Hoare triple {42#false} ~cond := #in~cond; {42#false} is VALID [2022-04-15 07:47:45,170 INFO L290 TraceCheckUtils]: 15: Hoare triple {42#false} assume 0 == ~cond; {42#false} is VALID [2022-04-15 07:47:45,171 INFO L290 TraceCheckUtils]: 16: Hoare triple {42#false} assume !false; {42#false} is VALID [2022-04-15 07:47:45,171 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-15 07:47:45,171 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 07:47:45,172 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1009201955] [2022-04-15 07:47:45,172 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1009201955] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:47:45,172 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:47:45,173 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 07:47:45,176 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 07:47:45,176 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2054307977] [2022-04-15 07:47:45,176 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2054307977] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:47:45,177 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:47:45,177 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 07:47:45,177 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1890075686] [2022-04-15 07:47:45,177 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 07:47:45,181 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-15 07:47:45,183 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 07:47:45,185 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-15 07:47:45,210 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-15 07:47:45,211 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-15 07:47:45,211 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 07:47:45,230 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-15 07:47:45,231 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 07:47:45,233 INFO L87 Difference]: Start difference. First operand has 38 states, 22 states have (on average 1.4090909090909092) internal successors, (31), 23 states have internal predecessors, (31), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-15 07:47:45,426 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:45,426 INFO L93 Difference]: Finished difference Result 68 states and 101 transitions. [2022-04-15 07:47:45,426 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-15 07:47:45,427 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-15 07:47:45,427 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 07:47:45,428 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-15 07:47:45,433 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 101 transitions. [2022-04-15 07:47:45,434 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-15 07:47:45,437 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 101 transitions. [2022-04-15 07:47:45,437 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 101 transitions. [2022-04-15 07:47:45,527 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 101 edges. 101 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:47:45,533 INFO L225 Difference]: With dead ends: 68 [2022-04-15 07:47:45,533 INFO L226 Difference]: Without dead ends: 34 [2022-04-15 07:47:45,536 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-15 07:47:45,538 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 49 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 07:47:45,538 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 49 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 07:47:45,548 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2022-04-15 07:47:45,557 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 33. [2022-04-15 07:47:45,558 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 07:47:45,558 INFO L82 GeneralOperation]: Start isEquivalent. First operand 34 states. Second operand has 33 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 07:47:45,559 INFO L74 IsIncluded]: Start isIncluded. First operand 34 states. Second operand has 33 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 07:47:45,559 INFO L87 Difference]: Start difference. First operand 34 states. Second operand has 33 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 07:47:45,562 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:45,562 INFO L93 Difference]: Finished difference Result 34 states and 43 transitions. [2022-04-15 07:47:45,562 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 43 transitions. [2022-04-15 07:47:45,563 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:47:45,563 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:47:45,563 INFO L74 IsIncluded]: Start isIncluded. First operand has 33 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 34 states. [2022-04-15 07:47:45,564 INFO L87 Difference]: Start difference. First operand has 33 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 34 states. [2022-04-15 07:47:45,566 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:45,566 INFO L93 Difference]: Finished difference Result 34 states and 43 transitions. [2022-04-15 07:47:45,566 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 43 transitions. [2022-04-15 07:47:45,567 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:47:45,567 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:47:45,567 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 07:47:45,567 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 07:47:45,568 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 07:47:45,570 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 42 transitions. [2022-04-15 07:47:45,571 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 42 transitions. Word has length 17 [2022-04-15 07:47:45,571 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 07:47:45,571 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 42 transitions. [2022-04-15 07:47:45,571 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-15 07:47:45,571 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 33 states and 42 transitions. [2022-04-15 07:47:45,609 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 42 edges. 42 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:47:45,609 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 42 transitions. [2022-04-15 07:47:45,610 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-15 07:47:45,610 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 07:47:45,610 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-15 07:47:45,610 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-15 07:47:45,610 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 07:47:45,611 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 07:47:45,611 INFO L85 PathProgramCache]: Analyzing trace with hash 766070672, now seen corresponding path program 1 times [2022-04-15 07:47:45,611 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 07:47:45,611 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [93178729] [2022-04-15 07:47:45,612 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 07:47:45,612 INFO L85 PathProgramCache]: Analyzing trace with hash 766070672, now seen corresponding path program 2 times [2022-04-15 07:47:45,612 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 07:47:45,612 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1230856605] [2022-04-15 07:47:45,612 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:47:45,612 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 07:47:45,654 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 07:47:45,654 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [816961185] [2022-04-15 07:47:45,654 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 07:47:45,655 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 07:47:45,655 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 07:47:45,656 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-15 07:47:45,656 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-15 07:47:45,692 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-15 07:47:45,692 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 07:47:45,696 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-15 07:47:45,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:47:45,728 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 07:47:45,897 INFO L272 TraceCheckUtils]: 0: Hoare triple {323#true} call ULTIMATE.init(); {323#true} is VALID [2022-04-15 07:47:45,897 INFO L290 TraceCheckUtils]: 1: Hoare triple {323#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {331#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:45,898 INFO L290 TraceCheckUtils]: 2: Hoare triple {331#(<= ~counter~0 0)} assume true; {331#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:45,898 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {331#(<= ~counter~0 0)} {323#true} #93#return; {331#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:45,899 INFO L272 TraceCheckUtils]: 4: Hoare triple {331#(<= ~counter~0 0)} call #t~ret8 := main(); {331#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:45,899 INFO L290 TraceCheckUtils]: 5: Hoare triple {331#(<= ~counter~0 0)} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {331#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:45,900 INFO L272 TraceCheckUtils]: 6: Hoare triple {331#(<= ~counter~0 0)} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {331#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:45,900 INFO L290 TraceCheckUtils]: 7: Hoare triple {331#(<= ~counter~0 0)} ~cond := #in~cond; {331#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:45,901 INFO L290 TraceCheckUtils]: 8: Hoare triple {331#(<= ~counter~0 0)} assume !(0 == ~cond); {331#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:45,901 INFO L290 TraceCheckUtils]: 9: Hoare triple {331#(<= ~counter~0 0)} assume true; {331#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:45,902 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {331#(<= ~counter~0 0)} {331#(<= ~counter~0 0)} #77#return; {331#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:45,902 INFO L290 TraceCheckUtils]: 11: Hoare triple {331#(<= ~counter~0 0)} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {331#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:45,903 INFO L290 TraceCheckUtils]: 12: Hoare triple {331#(<= ~counter~0 0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {365#(<= |main_#t~post6| 0)} is VALID [2022-04-15 07:47:45,903 INFO L290 TraceCheckUtils]: 13: Hoare triple {365#(<= |main_#t~post6| 0)} assume !(#t~post6 < 1);havoc #t~post6; {324#false} is VALID [2022-04-15 07:47:45,903 INFO L272 TraceCheckUtils]: 14: Hoare triple {324#false} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {324#false} is VALID [2022-04-15 07:47:45,903 INFO L290 TraceCheckUtils]: 15: Hoare triple {324#false} ~cond := #in~cond; {324#false} is VALID [2022-04-15 07:47:45,904 INFO L290 TraceCheckUtils]: 16: Hoare triple {324#false} assume 0 == ~cond; {324#false} is VALID [2022-04-15 07:47:45,904 INFO L290 TraceCheckUtils]: 17: Hoare triple {324#false} assume !false; {324#false} is VALID [2022-04-15 07:47:45,904 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-15 07:47:45,904 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 07:47:45,904 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 07:47:45,905 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1230856605] [2022-04-15 07:47:45,905 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 07:47:45,905 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [816961185] [2022-04-15 07:47:45,905 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [816961185] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:47:45,905 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:47:45,905 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-15 07:47:45,906 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 07:47:45,906 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [93178729] [2022-04-15 07:47:45,906 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [93178729] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:47:45,906 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:47:45,906 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-15 07:47:45,906 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1110100248] [2022-04-15 07:47:45,907 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 07:47:45,907 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-15 07:47:45,907 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 07:47:45,907 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-15 07:47:45,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-15 07:47:45,921 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-15 07:47:45,922 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 07:47:45,922 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-15 07:47:45,922 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-15 07:47:45,923 INFO L87 Difference]: Start difference. First operand 33 states and 42 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-15 07:47:46,008 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:46,008 INFO L93 Difference]: Finished difference Result 42 states and 51 transitions. [2022-04-15 07:47:46,008 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-15 07:47:46,008 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-15 07:47:46,009 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 07:47:46,009 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-15 07:47:46,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 51 transitions. [2022-04-15 07:47:46,010 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-15 07:47:46,011 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 51 transitions. [2022-04-15 07:47:46,012 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 4 states and 51 transitions. [2022-04-15 07:47:46,046 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 51 edges. 51 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:47:46,048 INFO L225 Difference]: With dead ends: 42 [2022-04-15 07:47:46,048 INFO L226 Difference]: Without dead ends: 35 [2022-04-15 07:47:46,048 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-15 07:47:46,049 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 07:47:46,049 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 107 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 07:47:46,050 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-04-15 07:47:46,059 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2022-04-15 07:47:46,059 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 07:47:46,059 INFO L82 GeneralOperation]: Start isEquivalent. First operand 35 states. Second operand has 35 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 22 states have internal predecessors, (26), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 07:47:46,060 INFO L74 IsIncluded]: Start isIncluded. First operand 35 states. Second operand has 35 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 22 states have internal predecessors, (26), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 07:47:46,060 INFO L87 Difference]: Start difference. First operand 35 states. Second operand has 35 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 22 states have internal predecessors, (26), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 07:47:46,061 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:46,062 INFO L93 Difference]: Finished difference Result 35 states and 44 transitions. [2022-04-15 07:47:46,062 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 44 transitions. [2022-04-15 07:47:46,062 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:47:46,062 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:47:46,063 INFO L74 IsIncluded]: Start isIncluded. First operand has 35 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 22 states have internal predecessors, (26), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 35 states. [2022-04-15 07:47:46,063 INFO L87 Difference]: Start difference. First operand has 35 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 22 states have internal predecessors, (26), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 35 states. [2022-04-15 07:47:46,064 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:46,064 INFO L93 Difference]: Finished difference Result 35 states and 44 transitions. [2022-04-15 07:47:46,065 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 44 transitions. [2022-04-15 07:47:46,065 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:47:46,065 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:47:46,065 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 07:47:46,065 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 07:47:46,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 22 states have internal predecessors, (26), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 07:47:46,067 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 44 transitions. [2022-04-15 07:47:46,067 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 44 transitions. Word has length 18 [2022-04-15 07:47:46,067 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 07:47:46,067 INFO L478 AbstractCegarLoop]: Abstraction has 35 states and 44 transitions. [2022-04-15 07:47:46,067 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-15 07:47:46,067 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 35 states and 44 transitions. [2022-04-15 07:47:46,100 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-15 07:47:46,100 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 44 transitions. [2022-04-15 07:47:46,101 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-15 07:47:46,101 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 07:47:46,101 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-15 07:47:46,118 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-15 07:47:46,304 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-15 07:47:46,305 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 07:47:46,305 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 07:47:46,305 INFO L85 PathProgramCache]: Analyzing trace with hash 767560222, now seen corresponding path program 1 times [2022-04-15 07:47:46,305 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 07:47:46,305 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1124615231] [2022-04-15 07:47:46,307 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 07:47:46,307 INFO L85 PathProgramCache]: Analyzing trace with hash 767560222, now seen corresponding path program 2 times [2022-04-15 07:47:46,307 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 07:47:46,307 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1734292182] [2022-04-15 07:47:46,307 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:47:46,307 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 07:47:46,318 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 07:47:46,318 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1282755627] [2022-04-15 07:47:46,318 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 07:47:46,318 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 07:47:46,319 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 07:47:46,319 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-15 07:47:46,320 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-15 07:47:46,349 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-15 07:47:46,349 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 07:47:46,350 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 07:47:46,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:47:46,359 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 07:47:46,435 INFO L272 TraceCheckUtils]: 0: Hoare triple {604#true} call ULTIMATE.init(); {604#true} is VALID [2022-04-15 07:47:46,436 INFO L290 TraceCheckUtils]: 1: Hoare triple {604#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {604#true} is VALID [2022-04-15 07:47:46,436 INFO L290 TraceCheckUtils]: 2: Hoare triple {604#true} assume true; {604#true} is VALID [2022-04-15 07:47:46,436 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {604#true} {604#true} #93#return; {604#true} is VALID [2022-04-15 07:47:46,436 INFO L272 TraceCheckUtils]: 4: Hoare triple {604#true} call #t~ret8 := main(); {604#true} is VALID [2022-04-15 07:47:46,436 INFO L290 TraceCheckUtils]: 5: Hoare triple {604#true} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {604#true} is VALID [2022-04-15 07:47:46,436 INFO L272 TraceCheckUtils]: 6: Hoare triple {604#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {604#true} is VALID [2022-04-15 07:47:46,436 INFO L290 TraceCheckUtils]: 7: Hoare triple {604#true} ~cond := #in~cond; {604#true} is VALID [2022-04-15 07:47:46,437 INFO L290 TraceCheckUtils]: 8: Hoare triple {604#true} assume !(0 == ~cond); {604#true} is VALID [2022-04-15 07:47:46,437 INFO L290 TraceCheckUtils]: 9: Hoare triple {604#true} assume true; {604#true} is VALID [2022-04-15 07:47:46,437 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {604#true} {604#true} #77#return; {604#true} is VALID [2022-04-15 07:47:46,437 INFO L290 TraceCheckUtils]: 11: Hoare triple {604#true} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {642#(and (= main_~a~0 0) (= main_~b~0 0))} is VALID [2022-04-15 07:47:46,438 INFO L290 TraceCheckUtils]: 12: Hoare triple {642#(and (= main_~a~0 0) (= main_~b~0 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {642#(and (= main_~a~0 0) (= main_~b~0 0))} is VALID [2022-04-15 07:47:46,438 INFO L290 TraceCheckUtils]: 13: Hoare triple {642#(and (= main_~a~0 0) (= main_~b~0 0))} assume !!(#t~post6 < 1);havoc #t~post6; {642#(and (= main_~a~0 0) (= main_~b~0 0))} is VALID [2022-04-15 07:47:46,439 INFO L272 TraceCheckUtils]: 14: Hoare triple {642#(and (= main_~a~0 0) (= main_~b~0 0))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {652#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 07:47:46,439 INFO L290 TraceCheckUtils]: 15: Hoare triple {652#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {656#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 07:47:46,440 INFO L290 TraceCheckUtils]: 16: Hoare triple {656#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {605#false} is VALID [2022-04-15 07:47:46,440 INFO L290 TraceCheckUtils]: 17: Hoare triple {605#false} assume !false; {605#false} is VALID [2022-04-15 07:47:46,440 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-15 07:47:46,440 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 07:47:46,440 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 07:47:46,440 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1734292182] [2022-04-15 07:47:46,440 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 07:47:46,440 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1282755627] [2022-04-15 07:47:46,441 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1282755627] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:47:46,441 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:47:46,441 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 07:47:46,441 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 07:47:46,441 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1124615231] [2022-04-15 07:47:46,441 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1124615231] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:47:46,441 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:47:46,441 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 07:47:46,441 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [393882108] [2022-04-15 07:47:46,441 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 07:47:46,442 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-15 07:47:46,442 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 07:47:46,442 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-15 07:47:46,452 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-15 07:47:46,452 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 07:47:46,452 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 07:47:46,453 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 07:47:46,453 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 07:47:46,453 INFO L87 Difference]: Start difference. First operand 35 states and 44 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-15 07:47:46,600 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:46,600 INFO L93 Difference]: Finished difference Result 45 states and 56 transitions. [2022-04-15 07:47:46,600 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 07:47:46,600 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-15 07:47:46,601 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 07:47:46,601 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-15 07:47:46,602 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 56 transitions. [2022-04-15 07:47:46,602 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-15 07:47:46,603 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 56 transitions. [2022-04-15 07:47:46,603 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 56 transitions. [2022-04-15 07:47:46,644 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 56 edges. 56 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:47:46,645 INFO L225 Difference]: With dead ends: 45 [2022-04-15 07:47:46,645 INFO L226 Difference]: Without dead ends: 43 [2022-04-15 07:47:46,646 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-15 07:47:46,646 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 6 mSDsluCounter, 104 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 07:47:46,647 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 145 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 07:47:46,647 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2022-04-15 07:47:46,660 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 40. [2022-04-15 07:47:46,660 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 07:47:46,660 INFO L82 GeneralOperation]: Start isEquivalent. First operand 43 states. Second operand has 40 states, 24 states have (on average 1.2083333333333333) internal successors, (29), 26 states have internal predecessors, (29), 11 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-15 07:47:46,661 INFO L74 IsIncluded]: Start isIncluded. First operand 43 states. Second operand has 40 states, 24 states have (on average 1.2083333333333333) internal successors, (29), 26 states have internal predecessors, (29), 11 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-15 07:47:46,661 INFO L87 Difference]: Start difference. First operand 43 states. Second operand has 40 states, 24 states have (on average 1.2083333333333333) internal successors, (29), 26 states have internal predecessors, (29), 11 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-15 07:47:46,663 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:46,663 INFO L93 Difference]: Finished difference Result 43 states and 54 transitions. [2022-04-15 07:47:46,663 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 54 transitions. [2022-04-15 07:47:46,664 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:47:46,664 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:47:46,664 INFO L74 IsIncluded]: Start isIncluded. First operand has 40 states, 24 states have (on average 1.2083333333333333) internal successors, (29), 26 states have internal predecessors, (29), 11 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) Second operand 43 states. [2022-04-15 07:47:46,664 INFO L87 Difference]: Start difference. First operand has 40 states, 24 states have (on average 1.2083333333333333) internal successors, (29), 26 states have internal predecessors, (29), 11 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) Second operand 43 states. [2022-04-15 07:47:46,665 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:46,666 INFO L93 Difference]: Finished difference Result 43 states and 54 transitions. [2022-04-15 07:47:46,666 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 54 transitions. [2022-04-15 07:47:46,666 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:47:46,666 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:47:46,666 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 07:47:46,666 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 07:47:46,667 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 24 states have (on average 1.2083333333333333) internal successors, (29), 26 states have internal predecessors, (29), 11 states have call successors, (11), 5 states have call predecessors, (11), 4 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-15 07:47:46,668 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 49 transitions. [2022-04-15 07:47:46,668 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 49 transitions. Word has length 18 [2022-04-15 07:47:46,668 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 07:47:46,668 INFO L478 AbstractCegarLoop]: Abstraction has 40 states and 49 transitions. [2022-04-15 07:47:46,668 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-15 07:47:46,668 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 40 states and 49 transitions. [2022-04-15 07:47:46,701 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 49 edges. 49 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:47:46,701 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 49 transitions. [2022-04-15 07:47:46,702 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-15 07:47:46,702 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 07:47:46,702 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] [2022-04-15 07:47:46,723 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-15 07:47:46,915 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-15 07:47:46,915 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 07:47:46,916 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 07:47:46,916 INFO L85 PathProgramCache]: Analyzing trace with hash -1016228092, now seen corresponding path program 1 times [2022-04-15 07:47:46,916 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 07:47:46,916 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1518794726] [2022-04-15 07:47:46,917 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 07:47:46,917 INFO L85 PathProgramCache]: Analyzing trace with hash -1016228092, now seen corresponding path program 2 times [2022-04-15 07:47:46,917 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 07:47:46,917 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [412883777] [2022-04-15 07:47:46,917 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:47:46,917 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 07:47:46,926 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 07:47:46,927 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [789325385] [2022-04-15 07:47:46,927 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 07:47:46,927 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 07:47:46,927 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 07:47:46,928 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-15 07:47:46,929 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-15 07:47:46,965 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 07:47:46,965 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 07:47:46,966 INFO L263 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 07:47:46,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:47:46,971 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 07:47:47,050 INFO L272 TraceCheckUtils]: 0: Hoare triple {920#true} call ULTIMATE.init(); {920#true} is VALID [2022-04-15 07:47:47,050 INFO L290 TraceCheckUtils]: 1: Hoare triple {920#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {920#true} is VALID [2022-04-15 07:47:47,050 INFO L290 TraceCheckUtils]: 2: Hoare triple {920#true} assume true; {920#true} is VALID [2022-04-15 07:47:47,050 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {920#true} {920#true} #93#return; {920#true} is VALID [2022-04-15 07:47:47,051 INFO L272 TraceCheckUtils]: 4: Hoare triple {920#true} call #t~ret8 := main(); {920#true} is VALID [2022-04-15 07:47:47,051 INFO L290 TraceCheckUtils]: 5: Hoare triple {920#true} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {920#true} is VALID [2022-04-15 07:47:47,051 INFO L272 TraceCheckUtils]: 6: Hoare triple {920#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {920#true} is VALID [2022-04-15 07:47:47,051 INFO L290 TraceCheckUtils]: 7: Hoare triple {920#true} ~cond := #in~cond; {920#true} is VALID [2022-04-15 07:47:47,051 INFO L290 TraceCheckUtils]: 8: Hoare triple {920#true} assume !(0 == ~cond); {920#true} is VALID [2022-04-15 07:47:47,051 INFO L290 TraceCheckUtils]: 9: Hoare triple {920#true} assume true; {920#true} is VALID [2022-04-15 07:47:47,051 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {920#true} {920#true} #77#return; {920#true} is VALID [2022-04-15 07:47:47,052 INFO L290 TraceCheckUtils]: 11: Hoare triple {920#true} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {958#(and (= main_~x~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 07:47:47,052 INFO L290 TraceCheckUtils]: 12: Hoare triple {958#(and (= main_~x~0 main_~r~0) (= main_~q~0 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {958#(and (= main_~x~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 07:47:47,053 INFO L290 TraceCheckUtils]: 13: Hoare triple {958#(and (= main_~x~0 main_~r~0) (= main_~q~0 0))} assume !!(#t~post6 < 1);havoc #t~post6; {958#(and (= main_~x~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 07:47:47,053 INFO L272 TraceCheckUtils]: 14: Hoare triple {958#(and (= main_~x~0 main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {920#true} is VALID [2022-04-15 07:47:47,053 INFO L290 TraceCheckUtils]: 15: Hoare triple {920#true} ~cond := #in~cond; {920#true} is VALID [2022-04-15 07:47:47,053 INFO L290 TraceCheckUtils]: 16: Hoare triple {920#true} assume !(0 == ~cond); {920#true} is VALID [2022-04-15 07:47:47,053 INFO L290 TraceCheckUtils]: 17: Hoare triple {920#true} assume true; {920#true} is VALID [2022-04-15 07:47:47,054 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {920#true} {958#(and (= main_~x~0 main_~r~0) (= main_~q~0 0))} #79#return; {958#(and (= main_~x~0 main_~r~0) (= main_~q~0 0))} is VALID [2022-04-15 07:47:47,055 INFO L272 TraceCheckUtils]: 19: Hoare triple {958#(and (= main_~x~0 main_~r~0) (= main_~q~0 0))} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {983#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 07:47:47,055 INFO L290 TraceCheckUtils]: 20: Hoare triple {983#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {987#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 07:47:47,056 INFO L290 TraceCheckUtils]: 21: Hoare triple {987#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {921#false} is VALID [2022-04-15 07:47:47,056 INFO L290 TraceCheckUtils]: 22: Hoare triple {921#false} assume !false; {921#false} is VALID [2022-04-15 07:47:47,056 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-15 07:47:47,056 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 07:47:47,056 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 07:47:47,056 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [412883777] [2022-04-15 07:47:47,056 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 07:47:47,057 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [789325385] [2022-04-15 07:47:47,057 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [789325385] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:47:47,057 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:47:47,057 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 07:47:47,057 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 07:47:47,057 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1518794726] [2022-04-15 07:47:47,057 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1518794726] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:47:47,057 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:47:47,057 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 07:47:47,058 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [739866465] [2022-04-15 07:47:47,058 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 07:47:47,058 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-04-15 07:47:47,058 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 07:47:47,058 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 07:47:47,072 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 23 edges. 23 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:47:47,072 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 07:47:47,072 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 07:47:47,072 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 07:47:47,072 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 07:47:47,072 INFO L87 Difference]: Start difference. First operand 40 states and 49 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 07:47:47,258 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:47,258 INFO L93 Difference]: Finished difference Result 58 states and 74 transitions. [2022-04-15 07:47:47,258 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 07:47:47,258 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-04-15 07:47:47,259 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 07:47:47,259 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 07:47:47,263 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 71 transitions. [2022-04-15 07:47:47,263 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 07:47:47,267 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 71 transitions. [2022-04-15 07:47:47,267 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 71 transitions. [2022-04-15 07:47:47,318 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 71 edges. 71 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:47:47,319 INFO L225 Difference]: With dead ends: 58 [2022-04-15 07:47:47,319 INFO L226 Difference]: Without dead ends: 55 [2022-04-15 07:47:47,319 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 19 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-15 07:47:47,320 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 13 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 07:47:47,320 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [18 Valid, 139 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 07:47:47,321 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-04-15 07:47:47,338 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 54. [2022-04-15 07:47:47,338 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 07:47:47,338 INFO L82 GeneralOperation]: Start isEquivalent. First operand 55 states. Second operand has 54 states, 32 states have (on average 1.21875) internal successors, (39), 33 states have internal predecessors, (39), 16 states have call successors, (16), 6 states have call predecessors, (16), 5 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-15 07:47:47,339 INFO L74 IsIncluded]: Start isIncluded. First operand 55 states. Second operand has 54 states, 32 states have (on average 1.21875) internal successors, (39), 33 states have internal predecessors, (39), 16 states have call successors, (16), 6 states have call predecessors, (16), 5 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-15 07:47:47,339 INFO L87 Difference]: Start difference. First operand 55 states. Second operand has 54 states, 32 states have (on average 1.21875) internal successors, (39), 33 states have internal predecessors, (39), 16 states have call successors, (16), 6 states have call predecessors, (16), 5 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-15 07:47:47,341 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:47,341 INFO L93 Difference]: Finished difference Result 55 states and 70 transitions. [2022-04-15 07:47:47,342 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 70 transitions. [2022-04-15 07:47:47,342 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:47:47,342 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:47:47,343 INFO L74 IsIncluded]: Start isIncluded. First operand has 54 states, 32 states have (on average 1.21875) internal successors, (39), 33 states have internal predecessors, (39), 16 states have call successors, (16), 6 states have call predecessors, (16), 5 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) Second operand 55 states. [2022-04-15 07:47:47,343 INFO L87 Difference]: Start difference. First operand has 54 states, 32 states have (on average 1.21875) internal successors, (39), 33 states have internal predecessors, (39), 16 states have call successors, (16), 6 states have call predecessors, (16), 5 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) Second operand 55 states. [2022-04-15 07:47:47,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:47,345 INFO L93 Difference]: Finished difference Result 55 states and 70 transitions. [2022-04-15 07:47:47,345 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 70 transitions. [2022-04-15 07:47:47,346 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:47:47,346 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:47:47,346 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 07:47:47,346 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 07:47:47,346 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 32 states have (on average 1.21875) internal successors, (39), 33 states have internal predecessors, (39), 16 states have call successors, (16), 6 states have call predecessors, (16), 5 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-15 07:47:47,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 69 transitions. [2022-04-15 07:47:47,348 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 69 transitions. Word has length 23 [2022-04-15 07:47:47,348 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 07:47:47,349 INFO L478 AbstractCegarLoop]: Abstraction has 54 states and 69 transitions. [2022-04-15 07:47:47,349 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 07:47:47,349 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 54 states and 69 transitions. [2022-04-15 07:47:47,425 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 69 edges. 69 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:47:47,425 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 69 transitions. [2022-04-15 07:47:47,426 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2022-04-15 07:47:47,426 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 07:47:47,426 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, 1, 1] [2022-04-15 07:47:47,442 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-15 07:47:47,626 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-15 07:47:47,627 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 07:47:47,627 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 07:47:47,627 INFO L85 PathProgramCache]: Analyzing trace with hash 2019703110, now seen corresponding path program 1 times [2022-04-15 07:47:47,627 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 07:47:47,627 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1975874627] [2022-04-15 07:47:47,628 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 07:47:47,628 INFO L85 PathProgramCache]: Analyzing trace with hash 2019703110, now seen corresponding path program 2 times [2022-04-15 07:47:47,628 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 07:47:47,628 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [64520782] [2022-04-15 07:47:47,628 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:47:47,628 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 07:47:47,640 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 07:47:47,640 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [752192703] [2022-04-15 07:47:47,640 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 07:47:47,640 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 07:47:47,641 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 07:47:47,646 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-15 07:47:47,647 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-15 07:47:47,683 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 07:47:47,683 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 07:47:47,684 INFO L263 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 07:47:47,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:47:47,699 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 07:47:47,824 INFO L272 TraceCheckUtils]: 0: Hoare triple {1329#true} call ULTIMATE.init(); {1329#true} is VALID [2022-04-15 07:47:47,825 INFO L290 TraceCheckUtils]: 1: Hoare triple {1329#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1337#(<= 0 ~counter~0)} is VALID [2022-04-15 07:47:47,825 INFO L290 TraceCheckUtils]: 2: Hoare triple {1337#(<= 0 ~counter~0)} assume true; {1337#(<= 0 ~counter~0)} is VALID [2022-04-15 07:47:47,825 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1337#(<= 0 ~counter~0)} {1329#true} #93#return; {1337#(<= 0 ~counter~0)} is VALID [2022-04-15 07:47:47,826 INFO L272 TraceCheckUtils]: 4: Hoare triple {1337#(<= 0 ~counter~0)} call #t~ret8 := main(); {1337#(<= 0 ~counter~0)} is VALID [2022-04-15 07:47:47,827 INFO L290 TraceCheckUtils]: 5: Hoare triple {1337#(<= 0 ~counter~0)} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {1337#(<= 0 ~counter~0)} is VALID [2022-04-15 07:47:47,828 INFO L272 TraceCheckUtils]: 6: Hoare triple {1337#(<= 0 ~counter~0)} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1337#(<= 0 ~counter~0)} is VALID [2022-04-15 07:47:47,828 INFO L290 TraceCheckUtils]: 7: Hoare triple {1337#(<= 0 ~counter~0)} ~cond := #in~cond; {1337#(<= 0 ~counter~0)} is VALID [2022-04-15 07:47:47,828 INFO L290 TraceCheckUtils]: 8: Hoare triple {1337#(<= 0 ~counter~0)} assume !(0 == ~cond); {1337#(<= 0 ~counter~0)} is VALID [2022-04-15 07:47:47,829 INFO L290 TraceCheckUtils]: 9: Hoare triple {1337#(<= 0 ~counter~0)} assume true; {1337#(<= 0 ~counter~0)} is VALID [2022-04-15 07:47:47,829 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1337#(<= 0 ~counter~0)} {1337#(<= 0 ~counter~0)} #77#return; {1337#(<= 0 ~counter~0)} is VALID [2022-04-15 07:47:47,829 INFO L290 TraceCheckUtils]: 11: Hoare triple {1337#(<= 0 ~counter~0)} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {1337#(<= 0 ~counter~0)} is VALID [2022-04-15 07:47:47,830 INFO L290 TraceCheckUtils]: 12: Hoare triple {1337#(<= 0 ~counter~0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1371#(<= 1 ~counter~0)} is VALID [2022-04-15 07:47:47,830 INFO L290 TraceCheckUtils]: 13: Hoare triple {1371#(<= 1 ~counter~0)} assume !!(#t~post6 < 1);havoc #t~post6; {1371#(<= 1 ~counter~0)} is VALID [2022-04-15 07:47:47,831 INFO L272 TraceCheckUtils]: 14: Hoare triple {1371#(<= 1 ~counter~0)} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {1371#(<= 1 ~counter~0)} is VALID [2022-04-15 07:47:47,831 INFO L290 TraceCheckUtils]: 15: Hoare triple {1371#(<= 1 ~counter~0)} ~cond := #in~cond; {1371#(<= 1 ~counter~0)} is VALID [2022-04-15 07:47:47,831 INFO L290 TraceCheckUtils]: 16: Hoare triple {1371#(<= 1 ~counter~0)} assume !(0 == ~cond); {1371#(<= 1 ~counter~0)} is VALID [2022-04-15 07:47:47,832 INFO L290 TraceCheckUtils]: 17: Hoare triple {1371#(<= 1 ~counter~0)} assume true; {1371#(<= 1 ~counter~0)} is VALID [2022-04-15 07:47:47,832 INFO L284 TraceCheckUtils]: 18: Hoare quadruple {1371#(<= 1 ~counter~0)} {1371#(<= 1 ~counter~0)} #79#return; {1371#(<= 1 ~counter~0)} is VALID [2022-04-15 07:47:47,834 INFO L272 TraceCheckUtils]: 19: Hoare triple {1371#(<= 1 ~counter~0)} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {1371#(<= 1 ~counter~0)} is VALID [2022-04-15 07:47:47,836 INFO L290 TraceCheckUtils]: 20: Hoare triple {1371#(<= 1 ~counter~0)} ~cond := #in~cond; {1371#(<= 1 ~counter~0)} is VALID [2022-04-15 07:47:47,836 INFO L290 TraceCheckUtils]: 21: Hoare triple {1371#(<= 1 ~counter~0)} assume !(0 == ~cond); {1371#(<= 1 ~counter~0)} is VALID [2022-04-15 07:47:47,836 INFO L290 TraceCheckUtils]: 22: Hoare triple {1371#(<= 1 ~counter~0)} assume true; {1371#(<= 1 ~counter~0)} is VALID [2022-04-15 07:47:47,837 INFO L284 TraceCheckUtils]: 23: Hoare quadruple {1371#(<= 1 ~counter~0)} {1371#(<= 1 ~counter~0)} #81#return; {1371#(<= 1 ~counter~0)} is VALID [2022-04-15 07:47:47,837 INFO L290 TraceCheckUtils]: 24: Hoare triple {1371#(<= 1 ~counter~0)} assume !!(~r~0 >= ~y~0);~a~0 := 1;~b~0 := ~y~0; {1371#(<= 1 ~counter~0)} is VALID [2022-04-15 07:47:47,838 INFO L290 TraceCheckUtils]: 25: Hoare triple {1371#(<= 1 ~counter~0)} #t~post7 := ~counter~0;~counter~0 := 1 + #t~post7; {1411#(<= 1 |main_#t~post7|)} is VALID [2022-04-15 07:47:47,838 INFO L290 TraceCheckUtils]: 26: Hoare triple {1411#(<= 1 |main_#t~post7|)} assume !!(#t~post7 < 1);havoc #t~post7; {1330#false} is VALID [2022-04-15 07:47:47,838 INFO L272 TraceCheckUtils]: 27: Hoare triple {1330#false} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {1330#false} is VALID [2022-04-15 07:47:47,838 INFO L290 TraceCheckUtils]: 28: Hoare triple {1330#false} ~cond := #in~cond; {1330#false} is VALID [2022-04-15 07:47:47,838 INFO L290 TraceCheckUtils]: 29: Hoare triple {1330#false} assume 0 == ~cond; {1330#false} is VALID [2022-04-15 07:47:47,838 INFO L290 TraceCheckUtils]: 30: Hoare triple {1330#false} assume !false; {1330#false} is VALID [2022-04-15 07:47:47,839 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-15 07:47:47,839 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 07:47:47,839 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 07:47:47,839 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [64520782] [2022-04-15 07:47:47,839 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 07:47:47,839 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [752192703] [2022-04-15 07:47:47,839 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [752192703] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:47:47,839 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:47:47,839 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 07:47:47,840 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 07:47:47,840 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1975874627] [2022-04-15 07:47:47,840 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1975874627] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:47:47,840 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:47:47,840 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 07:47:47,840 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1960251880] [2022-04-15 07:47:47,840 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 07:47:47,840 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Word has length 31 [2022-04-15 07:47:47,841 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 07:47:47,841 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-15 07:47:47,860 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 28 edges. 28 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:47:47,860 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 07:47:47,860 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 07:47:47,860 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 07:47:47,860 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-15 07:47:47,861 INFO L87 Difference]: Start difference. First operand 54 states and 69 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-15 07:47:47,963 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:47,963 INFO L93 Difference]: Finished difference Result 75 states and 94 transitions. [2022-04-15 07:47:47,963 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 07:47:47,964 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Word has length 31 [2022-04-15 07:47:47,964 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 07:47:47,964 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-15 07:47:47,965 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 62 transitions. [2022-04-15 07:47:47,965 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-15 07:47:47,966 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 62 transitions. [2022-04-15 07:47:47,966 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 62 transitions. [2022-04-15 07:47:48,008 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 62 edges. 62 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:47:48,009 INFO L225 Difference]: With dead ends: 75 [2022-04-15 07:47:48,009 INFO L226 Difference]: Without dead ends: 42 [2022-04-15 07:47:48,009 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2022-04-15 07:47:48,010 INFO L913 BasicCegarLoop]: 27 mSDtfsCounter, 11 mSDsluCounter, 35 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 62 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 07:47:48,010 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 62 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 07:47:48,010 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2022-04-15 07:47:48,043 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 40. [2022-04-15 07:47:48,044 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 07:47:48,044 INFO L82 GeneralOperation]: Start isEquivalent. First operand 42 states. Second operand has 40 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-15 07:47:48,044 INFO L74 IsIncluded]: Start isIncluded. First operand 42 states. Second operand has 40 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-15 07:47:48,044 INFO L87 Difference]: Start difference. First operand 42 states. Second operand has 40 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-15 07:47:48,045 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:48,046 INFO L93 Difference]: Finished difference Result 42 states and 45 transitions. [2022-04-15 07:47:48,046 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 45 transitions. [2022-04-15 07:47:48,046 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:47:48,046 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:47:48,046 INFO L74 IsIncluded]: Start isIncluded. First operand has 40 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand 42 states. [2022-04-15 07:47:48,046 INFO L87 Difference]: Start difference. First operand has 40 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand 42 states. [2022-04-15 07:47:48,048 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:47:48,048 INFO L93 Difference]: Finished difference Result 42 states and 45 transitions. [2022-04-15 07:47:48,048 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 45 transitions. [2022-04-15 07:47:48,048 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:47:48,048 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:47:48,048 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 07:47:48,048 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 07:47:48,048 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-15 07:47:48,049 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 43 transitions. [2022-04-15 07:47:48,049 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 43 transitions. Word has length 31 [2022-04-15 07:47:48,050 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 07:47:48,050 INFO L478 AbstractCegarLoop]: Abstraction has 40 states and 43 transitions. [2022-04-15 07:47:48,050 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-15 07:47:48,050 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 40 states and 43 transitions. [2022-04-15 07:47:48,082 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 43 edges. 43 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:47:48,082 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 43 transitions. [2022-04-15 07:47:48,083 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-04-15 07:47:48,083 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 07:47:48,083 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 07:47:48,116 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-15 07:47:48,299 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-15 07:47:48,300 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 07:47:48,300 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 07:47:48,300 INFO L85 PathProgramCache]: Analyzing trace with hash 202176206, now seen corresponding path program 1 times [2022-04-15 07:47:48,300 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 07:47:48,300 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [127377240] [2022-04-15 07:47:51,739 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 2 HavocedVariables, 5 AssignedVariables, 1 ReadonlyVariables, Eigenvalues: {0={1=2}, 1={1=1, 2=2}}, 1 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-15 07:47:51,743 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-04-15 07:47:51,746 INFO L85 PathProgramCache]: Analyzing trace with hash -1923851590, now seen corresponding path program 1 times [2022-04-15 07:47:51,747 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 07:47:51,747 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1243889293] [2022-04-15 07:47:51,747 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:47:51,747 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 07:47:51,758 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 07:47:51,758 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1399859713] [2022-04-15 07:47:51,758 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:47:51,758 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 07:47:51,759 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 07:47:51,759 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-15 07:47:51,760 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-15 07:47:51,805 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:47:51,806 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-15 07:47:51,816 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:47:51,818 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 07:47:53,281 INFO L272 TraceCheckUtils]: 0: Hoare triple {1742#true} call ULTIMATE.init(); {1742#true} is VALID [2022-04-15 07:47:53,282 INFO L290 TraceCheckUtils]: 1: Hoare triple {1742#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1750#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:53,282 INFO L290 TraceCheckUtils]: 2: Hoare triple {1750#(<= ~counter~0 0)} assume true; {1750#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:53,283 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1750#(<= ~counter~0 0)} {1742#true} #93#return; {1750#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:53,284 INFO L272 TraceCheckUtils]: 4: Hoare triple {1750#(<= ~counter~0 0)} call #t~ret8 := main(); {1750#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:53,285 INFO L290 TraceCheckUtils]: 5: Hoare triple {1750#(<= ~counter~0 0)} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {1750#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:53,308 INFO L272 TraceCheckUtils]: 6: Hoare triple {1750#(<= ~counter~0 0)} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1750#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:53,308 INFO L290 TraceCheckUtils]: 7: Hoare triple {1750#(<= ~counter~0 0)} ~cond := #in~cond; {1750#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:53,308 INFO L290 TraceCheckUtils]: 8: Hoare triple {1750#(<= ~counter~0 0)} assume !(0 == ~cond); {1750#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:53,309 INFO L290 TraceCheckUtils]: 9: Hoare triple {1750#(<= ~counter~0 0)} assume true; {1750#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:53,309 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1750#(<= ~counter~0 0)} {1750#(<= ~counter~0 0)} #77#return; {1750#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:53,309 INFO L290 TraceCheckUtils]: 11: Hoare triple {1750#(<= ~counter~0 0)} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {1750#(<= ~counter~0 0)} is VALID [2022-04-15 07:47:53,321 INFO L290 TraceCheckUtils]: 12: Hoare triple {1750#(<= ~counter~0 0)} [97] L37-3-->L37-1_primed: Formula: (let ((.cse6 (= |v_main_#t~post7_9| |v_main_#t~post7_7|)) (.cse7 (= v_main_~b~0_16 v_main_~b~0_15)) (.cse5 (< v_~counter~0_15 1)) (.cse0 (<= v_main_~y~0_24 v_main_~r~0_22)) (.cse2 (<= 0 v_~counter~0_15)) (.cse4 (= v_main_~x~0_13 (+ v_main_~r~0_22 (* v_main_~q~0_14 v_main_~y~0_24)))) (.cse1 (= (* v_main_~y~0_24 v_main_~a~0_16) v_main_~b~0_16)) (.cse8 (= v_~counter~0_15 v_~counter~0_13)) (.cse9 (= v_main_~r~0_22 v_main_~r~0_21)) (.cse10 (= v_main_~a~0_16 v_main_~a~0_15)) (.cse11 (= |v_main_#t~post6_9| |v_main_#t~post6_7|))) (or (and (= 1 v_main_~a~0_15) (< v_main_~q~0_14 v_main_~q~0_13) .cse0 (= v_main_~r~0_21 (+ v_main_~r~0_22 (* v_main_~y~0_24 (+ v_main_~q~0_14 (* (- 1) v_main_~q~0_13))))) (= (+ (* v_main_~q~0_14 (- 2)) v_~counter~0_15 (* v_main_~q~0_13 2)) v_~counter~0_13) (= v_main_~y~0_24 v_main_~b~0_15) .cse1 .cse2 (forall ((v_it_1 Int)) (or (let ((.cse3 (+ (* v_it_1 2) v_~counter~0_15))) (and (< .cse3 1) (<= (+ v_main_~y~0_24 (* v_main_~y~0_24 v_it_1)) v_main_~r~0_22) (<= 0 .cse3))) (not (<= 1 v_it_1)) (not (<= (+ v_main_~q~0_14 v_it_1 1) v_main_~q~0_13)))) .cse4 .cse5) (and (= v_main_~q~0_14 v_main_~q~0_13) .cse6 .cse7 .cse8 (= v_main_~y~0_24 v_main_~y~0_24) .cse9 (= v_main_~x~0_13 v_main_~x~0_13) .cse10 .cse11) (and .cse6 (= v_main_~q~0_13 v_main_~q~0_14) .cse7 (or (not .cse5) (not .cse0) (not .cse2) (not .cse4) (not .cse1)) .cse8 .cse9 .cse10 .cse11))) InVars {main_~q~0=v_main_~q~0_14, ~counter~0=v_~counter~0_15, main_~x~0=v_main_~x~0_13, main_~y~0=v_main_~y~0_24, main_~b~0=v_main_~b~0_16, main_~r~0=v_main_~r~0_22, main_#t~post6=|v_main_#t~post6_9|, main_~a~0=v_main_~a~0_16, main_#t~post7=|v_main_#t~post7_9|} OutVars{main_~q~0=v_main_~q~0_13, ~counter~0=v_~counter~0_13, main_~x~0=v_main_~x~0_13, main_~y~0=v_main_~y~0_24, main_~b~0=v_main_~b~0_15, main_~r~0=v_main_~r~0_21, main_#t~post6=|v_main_#t~post6_7|, main_~a~0=v_main_~a~0_15, main_#t~post7=|v_main_#t~post7_7|} AuxVars[] AssignedVars[main_~q~0, ~counter~0, main_~b~0, main_~r~0, main_#t~post6, main_~a~0, main_#t~post7] {1784#(or (and (= (+ (* main_~q~0 main_~y~0) main_~r~0) main_~x~0) (exists ((v_main_~q~0_18 Int)) (and (< main_~q~0 (+ v_main_~q~0_18 (div (+ (* ~counter~0 (- 1)) (* v_main_~q~0_18 (- 2)) (* main_~q~0 2)) 2) 2)) (< v_main_~q~0_18 main_~q~0) (<= (* main_~q~0 2) (+ ~counter~0 (* v_main_~q~0_18 2))) (<= (+ main_~y~0 (* v_main_~q~0_18 main_~y~0)) (+ (* main_~q~0 main_~y~0) main_~r~0))))) (<= ~counter~0 0))} is VALID [2022-04-15 07:47:53,322 INFO L290 TraceCheckUtils]: 13: Hoare triple {1784#(or (and (= (+ (* main_~q~0 main_~y~0) main_~r~0) main_~x~0) (exists ((v_main_~q~0_18 Int)) (and (< main_~q~0 (+ v_main_~q~0_18 (div (+ (* ~counter~0 (- 1)) (* v_main_~q~0_18 (- 2)) (* main_~q~0 2)) 2) 2)) (< v_main_~q~0_18 main_~q~0) (<= (* main_~q~0 2) (+ ~counter~0 (* v_main_~q~0_18 2))) (<= (+ main_~y~0 (* v_main_~q~0_18 main_~y~0)) (+ (* main_~q~0 main_~y~0) main_~r~0))))) (<= ~counter~0 0))} [96] L37-1_primed-->L37-1: Formula: (and (= |v_main_#t~post6_1| v_~counter~0_2) (= v_~counter~0_1 (+ |v_main_#t~post6_1| 1))) InVars {~counter~0=v_~counter~0_2} OutVars{~counter~0=v_~counter~0_1, main_#t~post6=|v_main_#t~post6_1|} AuxVars[] AssignedVars[~counter~0, main_#t~post6] {1788#(or (<= |main_#t~post6| 0) (and (= (+ (* main_~q~0 main_~y~0) main_~r~0) main_~x~0) (exists ((v_main_~q~0_18 Int)) (and (< v_main_~q~0_18 main_~q~0) (< main_~q~0 (+ v_main_~q~0_18 2)) (<= (+ main_~y~0 (* v_main_~q~0_18 main_~y~0)) (+ (* main_~q~0 main_~y~0) main_~r~0)))) (< 0 (+ 2 (div (- |main_#t~post6|) 2)))))} is VALID [2022-04-15 07:47:53,324 INFO L290 TraceCheckUtils]: 14: Hoare triple {1788#(or (<= |main_#t~post6| 0) (and (= (+ (* main_~q~0 main_~y~0) main_~r~0) main_~x~0) (exists ((v_main_~q~0_18 Int)) (and (< v_main_~q~0_18 main_~q~0) (< main_~q~0 (+ v_main_~q~0_18 2)) (<= (+ main_~y~0 (* v_main_~q~0_18 main_~y~0)) (+ (* main_~q~0 main_~y~0) main_~r~0)))) (< 0 (+ 2 (div (- |main_#t~post6|) 2)))))} assume !(#t~post6 < 1);havoc #t~post6; {1792#(and (= (+ (* main_~q~0 main_~y~0) main_~r~0) main_~x~0) (exists ((v_main_~q~0_18 Int)) (and (< v_main_~q~0_18 main_~q~0) (< main_~q~0 (+ v_main_~q~0_18 2)) (<= (+ main_~y~0 (* v_main_~q~0_18 main_~y~0)) (+ (* main_~q~0 main_~y~0) main_~r~0)))))} is VALID [2022-04-15 07:47:53,325 INFO L272 TraceCheckUtils]: 15: Hoare triple {1792#(and (= (+ (* main_~q~0 main_~y~0) main_~r~0) main_~x~0) (exists ((v_main_~q~0_18 Int)) (and (< v_main_~q~0_18 main_~q~0) (< main_~q~0 (+ v_main_~q~0_18 2)) (<= (+ main_~y~0 (* v_main_~q~0_18 main_~y~0)) (+ (* main_~q~0 main_~y~0) main_~r~0)))))} call __VERIFIER_assert((if ~x~0 == ~q~0 * ~y~0 + ~r~0 then 1 else 0)); {1796#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 07:47:53,325 INFO L290 TraceCheckUtils]: 16: Hoare triple {1796#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1800#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 07:47:53,325 INFO L290 TraceCheckUtils]: 17: Hoare triple {1800#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1743#false} is VALID [2022-04-15 07:47:53,325 INFO L290 TraceCheckUtils]: 18: Hoare triple {1743#false} assume !false; {1743#false} is VALID [2022-04-15 07:47:53,326 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-15 07:47:53,326 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 07:47:53,326 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 07:47:53,326 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1243889293] [2022-04-15 07:47:53,326 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 07:47:53,326 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1399859713] [2022-04-15 07:47:53,326 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1399859713] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:47:53,326 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:47:53,326 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-15 07:48:00,130 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 07:48:00,130 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [127377240] [2022-04-15 07:48:00,130 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [127377240] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:48:00,131 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:48:00,131 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [19] imperfect sequences [] total 19 [2022-04-15 07:48:00,131 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [865948464] [2022-04-15 07:48:00,131 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 07:48:00,131 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 16 states have (on average 1.3125) internal successors, (21), 14 states have internal predecessors, (21), 5 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) Word has length 34 [2022-04-15 07:48:00,131 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 07:48:00,131 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 19 states, 16 states have (on average 1.3125) internal successors, (21), 14 states have internal predecessors, (21), 5 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-15 07:48:00,285 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 31 edges. 31 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:48:00,285 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-04-15 07:48:00,285 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 07:48:00,285 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-04-15 07:48:00,286 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=322, Unknown=0, NotChecked=0, Total=380 [2022-04-15 07:48:00,286 INFO L87 Difference]: Start difference. First operand 40 states and 43 transitions. Second operand has 19 states, 16 states have (on average 1.3125) internal successors, (21), 14 states have internal predecessors, (21), 5 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-15 07:48:00,894 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:48:00,894 INFO L93 Difference]: Finished difference Result 49 states and 52 transitions. [2022-04-15 07:48:00,894 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-04-15 07:48:00,895 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 16 states have (on average 1.3125) internal successors, (21), 14 states have internal predecessors, (21), 5 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) Word has length 34 [2022-04-15 07:48:00,895 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 07:48:00,895 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 16 states have (on average 1.3125) internal successors, (21), 14 states have internal predecessors, (21), 5 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-15 07:48:00,896 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 45 transitions. [2022-04-15 07:48:00,896 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 16 states have (on average 1.3125) internal successors, (21), 14 states have internal predecessors, (21), 5 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-15 07:48:00,897 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 45 transitions. [2022-04-15 07:48:00,897 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 20 states and 45 transitions. [2022-04-15 07:48:00,941 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 45 edges. 45 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:48:00,941 INFO L225 Difference]: With dead ends: 49 [2022-04-15 07:48:00,941 INFO L226 Difference]: Without dead ends: 39 [2022-04-15 07:48:00,942 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 114 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=92, Invalid=508, Unknown=0, NotChecked=0, Total=600 [2022-04-15 07:48:00,942 INFO L913 BasicCegarLoop]: 18 mSDtfsCounter, 29 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 199 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 321 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 199 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 96 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-15 07:48:00,943 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 121 Invalid, 321 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 199 Invalid, 0 Unknown, 96 Unchecked, 0.2s Time] [2022-04-15 07:48:00,943 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-04-15 07:48:00,992 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 38. [2022-04-15 07:48:00,992 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 07:48:00,992 INFO L82 GeneralOperation]: Start isEquivalent. First operand 39 states. Second operand has 38 states, 25 states have (on average 1.04) internal successors, (26), 26 states have internal predecessors, (26), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-15 07:48:00,992 INFO L74 IsIncluded]: Start isIncluded. First operand 39 states. Second operand has 38 states, 25 states have (on average 1.04) internal successors, (26), 26 states have internal predecessors, (26), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-15 07:48:00,992 INFO L87 Difference]: Start difference. First operand 39 states. Second operand has 38 states, 25 states have (on average 1.04) internal successors, (26), 26 states have internal predecessors, (26), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-15 07:48:00,993 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:48:00,994 INFO L93 Difference]: Finished difference Result 39 states and 40 transitions. [2022-04-15 07:48:00,994 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 40 transitions. [2022-04-15 07:48:00,994 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:48:00,994 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:48:00,994 INFO L74 IsIncluded]: Start isIncluded. First operand has 38 states, 25 states have (on average 1.04) internal successors, (26), 26 states have internal predecessors, (26), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) Second operand 39 states. [2022-04-15 07:48:00,994 INFO L87 Difference]: Start difference. First operand has 38 states, 25 states have (on average 1.04) internal successors, (26), 26 states have internal predecessors, (26), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) Second operand 39 states. [2022-04-15 07:48:00,995 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:48:00,995 INFO L93 Difference]: Finished difference Result 39 states and 40 transitions. [2022-04-15 07:48:00,995 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 40 transitions. [2022-04-15 07:48:00,995 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:48:00,995 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:48:00,995 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 07:48:00,995 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 07:48:00,996 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 25 states have (on average 1.04) internal successors, (26), 26 states have internal predecessors, (26), 7 states have call successors, (7), 6 states have call predecessors, (7), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-15 07:48:00,996 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 39 transitions. [2022-04-15 07:48:00,996 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 39 transitions. Word has length 34 [2022-04-15 07:48:00,997 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 07:48:00,997 INFO L478 AbstractCegarLoop]: Abstraction has 38 states and 39 transitions. [2022-04-15 07:48:00,997 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 16 states have (on average 1.3125) internal successors, (21), 14 states have internal predecessors, (21), 5 states have call successors, (6), 4 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-15 07:48:00,997 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 38 states and 39 transitions. [2022-04-15 07:48:01,049 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 39 edges. 39 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:48:01,050 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 39 transitions. [2022-04-15 07:48:01,050 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-04-15 07:48:01,050 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 07:48:01,050 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 07:48:01,068 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-15 07:48:01,259 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-15 07:48:01,260 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 07:48:01,260 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 07:48:01,260 INFO L85 PathProgramCache]: Analyzing trace with hash 203665756, now seen corresponding path program 1 times [2022-04-15 07:48:01,260 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 07:48:01,260 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1239637321] [2022-04-15 07:48:07,802 INFO L89 AcceleratorJordan]: Jordan loop acceleration statistics: 2 HavocedVariables, 5 AssignedVariables, 1 ReadonlyVariables, Eigenvalues: {0={1=2}, 1={1=1, 2=2}}, 1 SequentialAcceleration, 0 AlternatingAcceleration, 0 QuantifierFreeResult [2022-04-15 07:48:07,804 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-04-15 07:48:07,806 INFO L85 PathProgramCache]: Analyzing trace with hash -90096376, now seen corresponding path program 1 times [2022-04-15 07:48:07,807 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 07:48:07,807 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1319629675] [2022-04-15 07:48:07,807 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:48:07,807 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 07:48:07,825 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 07:48:07,825 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1150573183] [2022-04-15 07:48:07,825 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:48:07,825 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 07:48:07,825 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 07:48:07,826 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-15 07:48:07,827 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-15 07:48:07,870 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:48:07,871 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 20 conjunts are in the unsatisfiable core [2022-04-15 07:48:07,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:48:07,883 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 07:48:10,949 INFO L272 TraceCheckUtils]: 0: Hoare triple {2080#true} call ULTIMATE.init(); {2080#true} is VALID [2022-04-15 07:48:10,951 INFO L290 TraceCheckUtils]: 1: Hoare triple {2080#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {2088#(<= 0 ~counter~0)} is VALID [2022-04-15 07:48:10,951 INFO L290 TraceCheckUtils]: 2: Hoare triple {2088#(<= 0 ~counter~0)} assume true; {2088#(<= 0 ~counter~0)} is VALID [2022-04-15 07:48:10,951 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {2088#(<= 0 ~counter~0)} {2080#true} #93#return; {2088#(<= 0 ~counter~0)} is VALID [2022-04-15 07:48:10,952 INFO L272 TraceCheckUtils]: 4: Hoare triple {2088#(<= 0 ~counter~0)} call #t~ret8 := main(); {2088#(<= 0 ~counter~0)} is VALID [2022-04-15 07:48:10,952 INFO L290 TraceCheckUtils]: 5: Hoare triple {2088#(<= 0 ~counter~0)} havoc ~x~0;havoc ~y~0;havoc ~q~0;havoc ~r~0;havoc ~a~0;havoc ~b~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~x~0 := #t~nondet4;havoc #t~nondet4;assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~y~0 := #t~nondet5;havoc #t~nondet5; {2088#(<= 0 ~counter~0)} is VALID [2022-04-15 07:48:10,953 INFO L272 TraceCheckUtils]: 6: Hoare triple {2088#(<= 0 ~counter~0)} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {2088#(<= 0 ~counter~0)} is VALID [2022-04-15 07:48:10,953 INFO L290 TraceCheckUtils]: 7: Hoare triple {2088#(<= 0 ~counter~0)} ~cond := #in~cond; {2107#(and (<= 0 ~counter~0) (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|))} is VALID [2022-04-15 07:48:10,953 INFO L290 TraceCheckUtils]: 8: Hoare triple {2107#(and (<= 0 ~counter~0) (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|))} assume !(0 == ~cond); {2111#(and (not (= |assume_abort_if_not_#in~cond| 0)) (<= 0 ~counter~0))} is VALID [2022-04-15 07:48:10,954 INFO L290 TraceCheckUtils]: 9: Hoare triple {2111#(and (not (= |assume_abort_if_not_#in~cond| 0)) (<= 0 ~counter~0))} assume true; {2111#(and (not (= |assume_abort_if_not_#in~cond| 0)) (<= 0 ~counter~0))} is VALID [2022-04-15 07:48:10,954 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {2111#(and (not (= |assume_abort_if_not_#in~cond| 0)) (<= 0 ~counter~0))} {2088#(<= 0 ~counter~0)} #77#return; {2118#(and (<= 0 ~counter~0) (<= 1 main_~y~0))} is VALID [2022-04-15 07:48:10,955 INFO L290 TraceCheckUtils]: 11: Hoare triple {2118#(and (<= 0 ~counter~0) (<= 1 main_~y~0))} ~q~0 := 0;~r~0 := ~x~0;~a~0 := 0;~b~0 := 0; {2122#(and (= main_~a~0 0) (= main_~b~0 0) (<= 0 ~counter~0) (<= 1 main_~y~0))} is VALID [2022-04-15 07:48:10,960 INFO L290 TraceCheckUtils]: 12: Hoare triple {2122#(and (= main_~a~0 0) (= main_~b~0 0) (<= 0 ~counter~0) (<= 1 main_~y~0))} [99] L37-3-->L37-1_primed: Formula: (let ((.cse5 (< v_~counter~0_26 1)) (.cse2 (<= v_main_~y~0_30 v_main_~r~0_32)) (.cse3 (= (* v_main_~y~0_30 v_main_~a~0_25) v_main_~b~0_25)) (.cse4 (<= 0 v_~counter~0_26)) (.cse6 (= v_main_~x~0_17 (+ v_main_~r~0_32 (* v_main_~q~0_24 v_main_~y~0_30)))) (.cse0 (= v_main_~r~0_32 v_main_~r~0_31)) (.cse1 (= v_main_~b~0_25 v_main_~b~0_24)) (.cse7 (= v_main_~q~0_24 v_main_~q~0_23)) (.cse8 (= |v_main_#t~post7_17| |v_main_#t~post7_15|)) (.cse9 (= |v_main_#t~post6_18| |v_main_#t~post6_16|)) (.cse10 (= v_~counter~0_26 v_~counter~0_24))) (or (and (= v_main_~a~0_24 v_main_~a~0_25) .cse0 .cse1 (or (not .cse2) (not .cse3) (not .cse4) (not .cse5) (not .cse6)) .cse7 .cse8 .cse9 .cse10) (and (= 1 v_main_~a~0_24) .cse5 (forall ((v_it_2 Int)) (or (not (<= 1 v_it_2)) (not (<= (+ v_main_~q~0_24 v_it_2 1) v_main_~q~0_23)) (let ((.cse11 (+ (* v_it_2 2) v_~counter~0_26))) (and (<= 0 .cse11) (<= (+ v_main_~y~0_30 (* v_main_~y~0_30 v_it_2)) v_main_~r~0_32) (< .cse11 1))))) (= (+ (* v_main_~q~0_23 2) (* v_main_~q~0_24 (- 2)) v_~counter~0_26) v_~counter~0_24) (= v_main_~r~0_31 (+ v_main_~r~0_32 (* v_main_~y~0_30 (+ v_main_~q~0_24 (* (- 1) v_main_~q~0_23))))) .cse2 (< v_main_~q~0_24 v_main_~q~0_23) (= v_main_~y~0_30 v_main_~b~0_24) .cse3 .cse4 .cse6) (and .cse0 (= v_main_~y~0_30 v_main_~y~0_30) (= v_main_~a~0_25 v_main_~a~0_24) .cse1 .cse7 .cse8 .cse9 .cse10 (= v_main_~x~0_17 v_main_~x~0_17)))) InVars {main_~q~0=v_main_~q~0_24, ~counter~0=v_~counter~0_26, main_~x~0=v_main_~x~0_17, main_~y~0=v_main_~y~0_30, main_~b~0=v_main_~b~0_25, main_~r~0=v_main_~r~0_32, main_#t~post6=|v_main_#t~post6_18|, main_~a~0=v_main_~a~0_25, main_#t~post7=|v_main_#t~post7_17|} OutVars{main_~q~0=v_main_~q~0_23, ~counter~0=v_~counter~0_24, main_~x~0=v_main_~x~0_17, main_~y~0=v_main_~y~0_30, main_~b~0=v_main_~b~0_24, main_~r~0=v_main_~r~0_31, main_#t~post6=|v_main_#t~post6_16|, main_~a~0=v_main_~a~0_24, main_#t~post7=|v_main_#t~post7_15|} AuxVars[] AssignedVars[main_~q~0, ~counter~0, main_~b~0, main_~r~0, main_#t~post6, main_~a~0, main_#t~post7] {2126#(and (or (and (= main_~a~0 1) (exists ((v_main_~q~0_28 Int) (main_~q~0 Int)) (and (<= (* main_~q~0 2) (+ ~counter~0 (* v_main_~q~0_28 2))) (< v_main_~q~0_28 main_~q~0) (< main_~q~0 (+ v_main_~q~0_28 (div (+ (* v_main_~q~0_28 (- 2)) (* ~counter~0 (- 1)) (* main_~q~0 2)) 2) 2)))) (= main_~b~0 main_~y~0)) (and (= main_~a~0 0) (= main_~b~0 0) (<= 0 ~counter~0))) (<= 1 main_~y~0))} is VALID [2022-04-15 07:48:10,961 INFO L290 TraceCheckUtils]: 13: Hoare triple {2126#(and (or (and (= main_~a~0 1) (exists ((v_main_~q~0_28 Int) (main_~q~0 Int)) (and (<= (* main_~q~0 2) (+ ~counter~0 (* v_main_~q~0_28 2))) (< v_main_~q~0_28 main_~q~0) (< main_~q~0 (+ v_main_~q~0_28 (div (+ (* v_main_~q~0_28 (- 2)) (* ~counter~0 (- 1)) (* main_~q~0 2)) 2) 2)))) (= main_~b~0 main_~y~0)) (and (= main_~a~0 0) (= main_~b~0 0) (<= 0 ~counter~0))) (<= 1 main_~y~0))} [98] L37-1_primed-->L37-1: Formula: (and (= |v_main_#t~post6_1| v_~counter~0_2) (= v_~counter~0_1 (+ |v_main_#t~post6_1| 1))) InVars {~counter~0=v_~counter~0_2} OutVars{~counter~0=v_~counter~0_1, main_#t~post6=|v_main_#t~post6_1|} AuxVars[] AssignedVars[~counter~0, main_#t~post6] {2130#(and (or (and (= main_~a~0 0) (= main_~b~0 0) (<= 0 |main_#t~post6|)) (and (= main_~a~0 1) (< (div |main_#t~post6| (- 2)) 0) (= main_~b~0 main_~y~0))) (<= 1 main_~y~0))} is VALID [2022-04-15 07:48:10,961 INFO L290 TraceCheckUtils]: 14: Hoare triple {2130#(and (or (and (= main_~a~0 0) (= main_~b~0 0) (<= 0 |main_#t~post6|)) (and (= main_~a~0 1) (< (div |main_#t~post6| (- 2)) 0) (= main_~b~0 main_~y~0))) (<= 1 main_~y~0))} assume !!(#t~post6 < 1);havoc #t~post6; {2134#(and (= main_~a~0 0) (= main_~b~0 0) (<= 1 main_~y~0))} is VALID [2022-04-15 07:48:10,962 INFO L272 TraceCheckUtils]: 15: Hoare triple {2134#(and (= main_~a~0 0) (= main_~b~0 0) (<= 1 main_~y~0))} call __VERIFIER_assert((if ~b~0 == ~y~0 * ~a~0 then 1 else 0)); {2138#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 07:48:10,962 INFO L290 TraceCheckUtils]: 16: Hoare triple {2138#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {2142#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 07:48:10,963 INFO L290 TraceCheckUtils]: 17: Hoare triple {2142#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {2081#false} is VALID [2022-04-15 07:48:10,963 INFO L290 TraceCheckUtils]: 18: Hoare triple {2081#false} assume !false; {2081#false} is VALID [2022-04-15 07:48:10,963 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-15 07:48:10,963 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 07:48:10,963 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 07:48:10,963 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1319629675] [2022-04-15 07:48:10,963 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 07:48:10,963 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1150573183] [2022-04-15 07:48:10,963 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1150573183] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:48:10,964 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:48:10,964 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-15 07:48:19,859 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 07:48:19,859 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1239637321] [2022-04-15 07:48:19,859 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1239637321] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:48:19,859 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:48:19,859 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [23] imperfect sequences [] total 23 [2022-04-15 07:48:19,859 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [343481915] [2022-04-15 07:48:19,859 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 07:48:19,860 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 20 states have (on average 1.15) internal successors, (23), 16 states have internal predecessors, (23), 5 states have call successors, (6), 5 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 34 [2022-04-15 07:48:19,860 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 07:48:19,860 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 23 states, 20 states have (on average 1.15) internal successors, (23), 16 states have internal predecessors, (23), 5 states have call successors, (6), 5 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-15 07:48:19,940 WARN L143 InductivityCheck]: Transition 2158#(and (= main_~a~0 1) (exists ((v_~counter~0_32 Int) (v_main_~y~0_BEFORE_CALL_11 Int) (v___VERIFIER_assert_~cond_BEFORE_RETURN_8 Int) (v_main_~a~0_BEFORE_CALL_7 Int) (v_main_~b~0_BEFORE_CALL_7 Int)) (and (or (and (= (+ main_~b~0 main_~r~0 (* (+ (* (- 1) main_~a~0) main_~q~0) main_~y~0)) main_~x~0) (= v___VERIFIER_assert_~cond_BEFORE_RETURN_8 1)) (and (= v___VERIFIER_assert_~cond_BEFORE_RETURN_8 0) (not (= (+ main_~b~0 main_~r~0 (* (+ (* (- 1) main_~a~0) main_~q~0) main_~y~0)) main_~x~0)))) (<= 1 v_main_~y~0_BEFORE_CALL_11) (or (and (= v_main_~b~0_BEFORE_CALL_7 (* v_main_~y~0_BEFORE_CALL_11 v_main_~a~0_BEFORE_CALL_7)) (= v___VERIFIER_assert_~cond_BEFORE_RETURN_8 1)) (and (= v___VERIFIER_assert_~cond_BEFORE_RETURN_8 0) (not (= v_main_~b~0_BEFORE_CALL_7 (* v_main_~y~0_BEFORE_CALL_11 v_main_~a~0_BEFORE_CALL_7))))) (or (and (exists ((v_main_~q~0_BEFORE_CALL_7 Int) (v_main_~q~0_29 Int) (v_main_~x~0_BEFORE_CALL_7 Int)) (and (forall ((v_it_2 Int)) (or (and (< (+ (* v_it_2 2) v_~counter~0_32) 1) (<= (+ (* v_main_~q~0_29 v_main_~y~0_BEFORE_CALL_11) (* v_it_2 v_main_~y~0_BEFORE_CALL_11) v_main_~y~0_BEFORE_CALL_11) v_main_~x~0_BEFORE_CALL_7) (<= 0 (+ (* v_it_2 2) v_~counter~0_32))) (not (<= 1 v_it_2)) (not (<= (+ v_main_~q~0_29 v_it_2 1) v_main_~q~0_BEFORE_CALL_7)))) (= (+ ~counter~0 (* v_main_~q~0_29 2)) (+ (* 2 v_main_~q~0_BEFORE_CALL_7) 2 v_~counter~0_32)) (<= (+ (* v_main_~q~0_29 v_main_~y~0_BEFORE_CALL_11) v_main_~y~0_BEFORE_CALL_11) v_main_~x~0_BEFORE_CALL_7) (< v_main_~q~0_29 v_main_~q~0_BEFORE_CALL_7))) (= v_main_~b~0_BEFORE_CALL_7 v_main_~y~0_BEFORE_CALL_11) (= v_main_~a~0_BEFORE_CALL_7 1) (< v_~counter~0_32 1)) (and (= v_main_~a~0_BEFORE_CALL_7 0) (= v_main_~b~0_BEFORE_CALL_7 0) (= ~counter~0 (+ 2 v_~counter~0_32)))) (<= 0 v_~counter~0_32))) (= main_~b~0 main_~y~0) (< ~counter~0 3) (<= main_~y~0 (+ main_~b~0 main_~r~0))) ( _ , #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; , 2130#(and (or (and (= main_~a~0 0) (= main_~b~0 0) (<= 0 |main_#t~post6|)) (and (= main_~a~0 1) (< (div |main_#t~post6| (- 2)) 0) (= main_~b~0 main_~y~0))) (<= 1 main_~y~0)) ) not inductive [2022-04-15 07:48:19,958 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-15 07:48:20,140 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-15 07:48:20,141 FATAL L? ?]: The Plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction has thrown an exception: java.lang.AssertionError: inductivity failed at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.predicates.InductivityCheck.evaluateResult(InductivityCheck.java:145) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.predicates.InductivityCheck.checkInductivity(InductivityCheck.java:103) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.predicates.InductivityCheck.(InductivityCheck.java:75) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.constructInterpolantAutomaton(BasicCegarLoop.java:682) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.constructRefinementAutomaton(AbstractCegarLoop.java:547) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:420) 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:411) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:301) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:261) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:174) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:153) 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-15 07:48:20,144 INFO L158 Benchmark]: Toolchain (without parser) took 35896.43ms. Allocated memory was 197.1MB in the beginning and 237.0MB in the end (delta: 39.8MB). Free memory was 146.4MB in the beginning and 202.6MB in the end (delta: -56.2MB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-15 07:48:20,144 INFO L158 Benchmark]: CDTParser took 0.11ms. Allocated memory is still 197.1MB. Free memory was 162.5MB in the beginning and 162.3MB in the end (delta: 151.8kB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-15 07:48:20,144 INFO L158 Benchmark]: CACSL2BoogieTranslator took 235.60ms. Allocated memory is still 197.1MB. Free memory was 146.1MB in the beginning and 171.8MB in the end (delta: -25.7MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2022-04-15 07:48:20,145 INFO L158 Benchmark]: Boogie Preprocessor took 35.20ms. Allocated memory is still 197.1MB. Free memory was 171.8MB in the beginning and 170.1MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-04-15 07:48:20,145 INFO L158 Benchmark]: RCFGBuilder took 309.31ms. Allocated memory is still 197.1MB. Free memory was 170.1MB in the beginning and 158.2MB in the end (delta: 11.9MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-15 07:48:20,145 INFO L158 Benchmark]: TraceAbstraction took 35312.76ms. Allocated memory was 197.1MB in the beginning and 237.0MB in the end (delta: 39.8MB). Free memory was 157.5MB in the beginning and 202.6MB in the end (delta: -45.1MB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-15 07:48:20,146 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 197.1MB. Free memory was 162.5MB in the beginning and 162.3MB in the end (delta: 151.8kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 235.60ms. Allocated memory is still 197.1MB. Free memory was 146.1MB in the beginning and 171.8MB in the end (delta: -25.7MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * Boogie Preprocessor took 35.20ms. Allocated memory is still 197.1MB. Free memory was 171.8MB in the beginning and 170.1MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 309.31ms. Allocated memory is still 197.1MB. Free memory was 170.1MB in the beginning and 158.2MB in the end (delta: 11.9MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * TraceAbstraction took 35312.76ms. Allocated memory was 197.1MB in the beginning and 237.0MB in the end (delta: 39.8MB). Free memory was 157.5MB in the beginning and 202.6MB in the end (delta: -45.1MB). There was no memory consumed. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - ExceptionOrErrorResult: AssertionError: inductivity failed de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: AssertionError: inductivity failed: de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.predicates.InductivityCheck.evaluateResult(InductivityCheck.java:145) RESULT: Ultimate could not prove your program: Toolchain returned no result. [2022-04-15 07:48:20,164 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...