/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/egcd-ll_unwindbound1.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-fb4f59a-m [2022-04-28 05:22:47,900 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-28 05:22:47,901 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-28 05:22:47,936 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-28 05:22:47,936 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-28 05:22:47,937 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-28 05:22:47,940 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-28 05:22:47,947 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-28 05:22:47,948 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-28 05:22:47,949 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-28 05:22:47,950 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-28 05:22:47,950 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-28 05:22:47,950 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-28 05:22:47,951 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-28 05:22:47,952 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-28 05:22:47,952 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-28 05:22:47,953 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-28 05:22:47,953 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-28 05:22:47,954 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-28 05:22:47,955 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-28 05:22:47,955 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-28 05:22:47,957 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-28 05:22:47,958 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-28 05:22:47,959 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-28 05:22:47,960 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-28 05:22:47,966 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-28 05:22:47,966 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-28 05:22:47,966 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-28 05:22:47,967 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-28 05:22:47,967 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-28 05:22:47,967 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-28 05:22:47,968 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-28 05:22:47,968 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-28 05:22:47,968 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-28 05:22:47,969 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-28 05:22:47,969 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-28 05:22:47,969 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-28 05:22:47,970 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-28 05:22:47,970 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-28 05:22:47,970 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-28 05:22:47,971 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-28 05:22:47,976 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-28 05:22:47,976 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-04-28 05:22:47,986 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-28 05:22:47,987 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-28 05:22:47,988 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-28 05:22:47,988 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-28 05:22:47,988 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-28 05:22:47,988 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-28 05:22:47,988 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-28 05:22:47,988 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-28 05:22:47,988 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-28 05:22:47,989 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-28 05:22:47,989 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-28 05:22:47,989 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-28 05:22:47,989 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-28 05:22:47,989 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-28 05:22:47,989 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-28 05:22:47,989 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-28 05:22:47,990 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-28 05:22:47,990 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-28 05:22:47,990 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-28 05:22:47,990 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-28 05:22:47,990 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-28 05:22:47,990 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-28 05:22:47,990 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-28 05:22:47,990 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-28 05:22:47,990 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-28 05:22:47,990 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-28 05:22:48,176 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-28 05:22:48,198 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-28 05:22:48,202 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-28 05:22:48,203 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-28 05:22:48,203 INFO L275 PluginConnector]: CDTParser initialized [2022-04-28 05:22:48,204 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd-ll_unwindbound1.c [2022-04-28 05:22:48,280 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ec8779d8a/377634a5d6704f72972b5d4418dec9ae/FLAG5ed842aa1 [2022-04-28 05:22:48,661 INFO L306 CDTParser]: Found 1 translation units. [2022-04-28 05:22:48,661 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd-ll_unwindbound1.c [2022-04-28 05:22:48,666 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ec8779d8a/377634a5d6704f72972b5d4418dec9ae/FLAG5ed842aa1 [2022-04-28 05:22:49,108 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ec8779d8a/377634a5d6704f72972b5d4418dec9ae [2022-04-28 05:22:49,110 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-28 05:22:49,111 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-28 05:22:49,112 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-28 05:22:49,112 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-28 05:22:49,114 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-28 05:22:49,115 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.04 05:22:49" (1/1) ... [2022-04-28 05:22:49,116 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6f1769a0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 05:22:49, skipping insertion in model container [2022-04-28 05:22:49,116 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.04 05:22:49" (1/1) ... [2022-04-28 05:22:49,120 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-28 05:22:49,129 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-28 05:22:49,244 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/egcd-ll_unwindbound1.c[489,502] [2022-04-28 05:22:49,259 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-28 05:22:49,266 INFO L203 MainTranslator]: Completed pre-run [2022-04-28 05:22:49,279 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/egcd-ll_unwindbound1.c[489,502] [2022-04-28 05:22:49,285 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-28 05:22:49,311 INFO L208 MainTranslator]: Completed translation [2022-04-28 05:22:49,312 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 05:22:49 WrapperNode [2022-04-28 05:22:49,312 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-28 05:22:49,313 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-28 05:22:49,313 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-28 05:22:49,313 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-28 05:22:49,322 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 05:22:49" (1/1) ... [2022-04-28 05:22:49,323 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 05:22:49" (1/1) ... [2022-04-28 05:22:49,329 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 05:22:49" (1/1) ... [2022-04-28 05:22:49,330 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 05:22:49" (1/1) ... [2022-04-28 05:22:49,336 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 05:22:49" (1/1) ... [2022-04-28 05:22:49,341 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 05:22:49" (1/1) ... [2022-04-28 05:22:49,342 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 05:22:49" (1/1) ... [2022-04-28 05:22:49,344 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-28 05:22:49,344 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-28 05:22:49,345 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-28 05:22:49,345 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-28 05:22:49,346 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 05:22:49" (1/1) ... [2022-04-28 05:22:49,367 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-28 05:22:49,374 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 05:22:49,393 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-28 05:22:49,396 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-28 05:22:49,419 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-28 05:22:49,419 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-28 05:22:49,419 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-28 05:22:49,419 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-28 05:22:49,419 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-28 05:22:49,419 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-28 05:22:49,419 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-28 05:22:49,419 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-28 05:22:49,419 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-28 05:22:49,420 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-28 05:22:49,420 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-28 05:22:49,420 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-28 05:22:49,420 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-28 05:22:49,420 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-28 05:22:49,420 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-28 05:22:49,420 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-28 05:22:49,420 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-28 05:22:49,420 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-28 05:22:49,420 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-28 05:22:49,420 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-28 05:22:49,463 INFO L234 CfgBuilder]: Building ICFG [2022-04-28 05:22:49,465 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-28 05:22:49,585 INFO L275 CfgBuilder]: Performing block encoding [2022-04-28 05:22:49,591 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-28 05:22:49,591 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-28 05:22:49,592 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.04 05:22:49 BoogieIcfgContainer [2022-04-28 05:22:49,592 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-28 05:22:49,594 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-28 05:22:49,594 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-28 05:22:49,596 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-28 05:22:49,596 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 28.04 05:22:49" (1/3) ... [2022-04-28 05:22:49,597 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1e49f48e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.04 05:22:49, skipping insertion in model container [2022-04-28 05:22:49,597 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 05:22:49" (2/3) ... [2022-04-28 05:22:49,597 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1e49f48e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.04 05:22:49, skipping insertion in model container [2022-04-28 05:22:49,597 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.04 05:22:49" (3/3) ... [2022-04-28 05:22:49,598 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd-ll_unwindbound1.c [2022-04-28 05:22:49,608 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-28 05:22:49,608 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-28 05:22:49,639 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-28 05:22:49,643 INFO L357 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, mPorIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@4e187dc1, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@45421c81 [2022-04-28 05:22:49,644 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-28 05:22:49,650 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 18 states have (on average 1.3888888888888888) internal successors, (25), 19 states have internal predecessors, (25), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 05:22:49,675 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-28 05:22:49,675 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 05:22:49,676 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 05:22:49,676 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 05:22:49,680 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 05:22:49,680 INFO L85 PathProgramCache]: Analyzing trace with hash 1226702723, now seen corresponding path program 1 times [2022-04-28 05:22:49,685 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 05:22:49,686 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2070260747] [2022-04-28 05:22:49,701 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 05:22:49,701 INFO L85 PathProgramCache]: Analyzing trace with hash 1226702723, now seen corresponding path program 2 times [2022-04-28 05:22:49,704 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 05:22:49,705 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2002429514] [2022-04-28 05:22:49,706 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 05:22:49,706 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 05:22:49,822 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 05:22:49,897 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-28 05:22:49,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 05:22:49,921 INFO L290 TraceCheckUtils]: 0: Hoare triple {51#(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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {38#true} is VALID [2022-04-28 05:22:49,921 INFO L290 TraceCheckUtils]: 1: Hoare triple {38#true} assume true; {38#true} is VALID [2022-04-28 05:22:49,921 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {38#true} {38#true} #82#return; {38#true} is VALID [2022-04-28 05:22:49,922 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-28 05:22:49,930 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 05:22:49,941 INFO L290 TraceCheckUtils]: 0: Hoare triple {38#true} ~cond := #in~cond; {38#true} is VALID [2022-04-28 05:22:49,942 INFO L290 TraceCheckUtils]: 1: Hoare triple {38#true} assume 0 == ~cond;assume false; {39#false} is VALID [2022-04-28 05:22:49,942 INFO L290 TraceCheckUtils]: 2: Hoare triple {39#false} assume true; {39#false} is VALID [2022-04-28 05:22:49,943 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {39#false} {38#true} #64#return; {39#false} is VALID [2022-04-28 05:22:49,943 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-28 05:22:49,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 05:22:49,954 INFO L290 TraceCheckUtils]: 0: Hoare triple {38#true} ~cond := #in~cond; {38#true} is VALID [2022-04-28 05:22:49,955 INFO L290 TraceCheckUtils]: 1: Hoare triple {38#true} assume 0 == ~cond;assume false; {39#false} is VALID [2022-04-28 05:22:49,956 INFO L290 TraceCheckUtils]: 2: Hoare triple {39#false} assume true; {39#false} is VALID [2022-04-28 05:22:49,956 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {39#false} {39#false} #66#return; {39#false} is VALID [2022-04-28 05:22:49,958 INFO L272 TraceCheckUtils]: 0: Hoare triple {38#true} call ULTIMATE.init(); {51#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-28 05:22:49,958 INFO L290 TraceCheckUtils]: 1: Hoare triple {51#(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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {38#true} is VALID [2022-04-28 05:22:49,958 INFO L290 TraceCheckUtils]: 2: Hoare triple {38#true} assume true; {38#true} is VALID [2022-04-28 05:22:49,958 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {38#true} {38#true} #82#return; {38#true} is VALID [2022-04-28 05:22:49,959 INFO L272 TraceCheckUtils]: 4: Hoare triple {38#true} call #t~ret7 := main(); {38#true} is VALID [2022-04-28 05:22:49,959 INFO L290 TraceCheckUtils]: 5: Hoare triple {38#true} havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~s~0;havoc ~x~0;havoc ~y~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; {38#true} is VALID [2022-04-28 05:22:49,959 INFO L272 TraceCheckUtils]: 6: Hoare triple {38#true} call assume_abort_if_not((if ~x~0 >= 1 then 1 else 0)); {38#true} is VALID [2022-04-28 05:22:49,959 INFO L290 TraceCheckUtils]: 7: Hoare triple {38#true} ~cond := #in~cond; {38#true} is VALID [2022-04-28 05:22:49,960 INFO L290 TraceCheckUtils]: 8: Hoare triple {38#true} assume 0 == ~cond;assume false; {39#false} is VALID [2022-04-28 05:22:49,961 INFO L290 TraceCheckUtils]: 9: Hoare triple {39#false} assume true; {39#false} is VALID [2022-04-28 05:22:49,961 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {39#false} {38#true} #64#return; {39#false} is VALID [2022-04-28 05:22:49,961 INFO L272 TraceCheckUtils]: 11: Hoare triple {39#false} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {38#true} is VALID [2022-04-28 05:22:49,961 INFO L290 TraceCheckUtils]: 12: Hoare triple {38#true} ~cond := #in~cond; {38#true} is VALID [2022-04-28 05:22:49,962 INFO L290 TraceCheckUtils]: 13: Hoare triple {38#true} assume 0 == ~cond;assume false; {39#false} is VALID [2022-04-28 05:22:49,962 INFO L290 TraceCheckUtils]: 14: Hoare triple {39#false} assume true; {39#false} is VALID [2022-04-28 05:22:49,962 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {39#false} {39#false} #66#return; {39#false} is VALID [2022-04-28 05:22:49,962 INFO L290 TraceCheckUtils]: 16: Hoare triple {39#false} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0;~r~0 := 0;~s~0 := 1; {39#false} is VALID [2022-04-28 05:22:49,962 INFO L290 TraceCheckUtils]: 17: Hoare triple {39#false} assume !true; {39#false} is VALID [2022-04-28 05:22:49,963 INFO L272 TraceCheckUtils]: 18: Hoare triple {39#false} call __VERIFIER_assert((if 0 == ~a~0 - ~b~0 then 1 else 0)); {39#false} is VALID [2022-04-28 05:22:49,963 INFO L290 TraceCheckUtils]: 19: Hoare triple {39#false} ~cond := #in~cond; {39#false} is VALID [2022-04-28 05:22:49,963 INFO L290 TraceCheckUtils]: 20: Hoare triple {39#false} assume 0 == ~cond; {39#false} is VALID [2022-04-28 05:22:49,963 INFO L290 TraceCheckUtils]: 21: Hoare triple {39#false} assume !false; {39#false} is VALID [2022-04-28 05:22:49,964 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-28 05:22:49,964 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 05:22:49,964 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2002429514] [2022-04-28 05:22:49,965 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2002429514] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 05:22:49,965 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 05:22:49,965 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-28 05:22:49,967 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 05:22:49,967 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2070260747] [2022-04-28 05:22:49,968 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2070260747] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 05:22:49,968 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 05:22:49,968 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-28 05:22:49,968 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1919623244] [2022-04-28 05:22:49,968 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 05:22:49,972 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, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-04-28 05:22:49,973 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 05:22:49,976 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, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 05:22:50,010 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 19 edges. 19 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:50,011 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-28 05:22:50,012 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 05:22:50,027 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-28 05:22:50,028 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-28 05:22:50,030 INFO L87 Difference]: Start difference. First operand has 35 states, 18 states have (on average 1.3888888888888888) internal successors, (25), 19 states have internal predecessors, (25), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) 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, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 05:22:50,212 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:50,212 INFO L93 Difference]: Finished difference Result 64 states and 97 transitions. [2022-04-28 05:22:50,212 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-28 05:22:50,213 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, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-04-28 05:22:50,213 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 05:22:50,214 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, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 05:22:50,220 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 97 transitions. [2022-04-28 05:22:50,220 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, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 05:22:50,225 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 97 transitions. [2022-04-28 05:22:50,226 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 97 transitions. [2022-04-28 05:22:50,315 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 97 edges. 97 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:50,321 INFO L225 Difference]: With dead ends: 64 [2022-04-28 05:22:50,321 INFO L226 Difference]: Without dead ends: 31 [2022-04-28 05:22:50,323 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-28 05:22:50,326 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-28 05:22:50,326 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 45 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-28 05:22:50,337 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2022-04-28 05:22:50,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 30. [2022-04-28 05:22:50,347 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 05:22:50,348 INFO L82 GeneralOperation]: Start isEquivalent. First operand 31 states. Second operand has 30 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 16 states have internal predecessors, (19), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-28 05:22:50,349 INFO L74 IsIncluded]: Start isIncluded. First operand 31 states. Second operand has 30 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 16 states have internal predecessors, (19), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-28 05:22:50,349 INFO L87 Difference]: Start difference. First operand 31 states. Second operand has 30 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 16 states have internal predecessors, (19), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-28 05:22:50,352 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:50,353 INFO L93 Difference]: Finished difference Result 31 states and 40 transitions. [2022-04-28 05:22:50,353 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 40 transitions. [2022-04-28 05:22:50,353 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 05:22:50,353 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 05:22:50,354 INFO L74 IsIncluded]: Start isIncluded. First operand has 30 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 16 states have internal predecessors, (19), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 31 states. [2022-04-28 05:22:50,354 INFO L87 Difference]: Start difference. First operand has 30 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 16 states have internal predecessors, (19), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 31 states. [2022-04-28 05:22:50,357 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:50,357 INFO L93 Difference]: Finished difference Result 31 states and 40 transitions. [2022-04-28 05:22:50,357 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 40 transitions. [2022-04-28 05:22:50,358 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 05:22:50,358 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 05:22:50,358 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 05:22:50,358 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 05:22:50,358 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 16 states have internal predecessors, (19), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-28 05:22:50,360 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2022-04-28 05:22:50,361 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 22 [2022-04-28 05:22:50,362 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 05:22:50,362 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2022-04-28 05:22:50,362 INFO L496 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, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 05:22:50,362 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 30 states and 39 transitions. [2022-04-28 05:22:50,396 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-28 05:22:50,396 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2022-04-28 05:22:50,396 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-28 05:22:50,396 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 05:22:50,397 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 05:22:50,397 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-28 05:22:50,397 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 05:22:50,398 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 05:22:50,398 INFO L85 PathProgramCache]: Analyzing trace with hash 1346542817, now seen corresponding path program 1 times [2022-04-28 05:22:50,398 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 05:22:50,398 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1667143280] [2022-04-28 05:22:50,398 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 05:22:50,398 INFO L85 PathProgramCache]: Analyzing trace with hash 1346542817, now seen corresponding path program 2 times [2022-04-28 05:22:50,399 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 05:22:50,399 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1765271716] [2022-04-28 05:22:50,399 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 05:22:50,399 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 05:22:50,417 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 05:22:50,454 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-28 05:22:50,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 05:22:50,465 INFO L290 TraceCheckUtils]: 0: Hoare triple {319#(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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {309#(= ~counter~0 0)} is VALID [2022-04-28 05:22:50,465 INFO L290 TraceCheckUtils]: 1: Hoare triple {309#(= ~counter~0 0)} assume true; {309#(= ~counter~0 0)} is VALID [2022-04-28 05:22:50,466 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {309#(= ~counter~0 0)} {304#true} #82#return; {309#(= ~counter~0 0)} is VALID [2022-04-28 05:22:50,466 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-28 05:22:50,468 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 05:22:50,471 INFO L290 TraceCheckUtils]: 0: Hoare triple {304#true} ~cond := #in~cond; {304#true} is VALID [2022-04-28 05:22:50,472 INFO L290 TraceCheckUtils]: 1: Hoare triple {304#true} assume !(0 == ~cond); {304#true} is VALID [2022-04-28 05:22:50,472 INFO L290 TraceCheckUtils]: 2: Hoare triple {304#true} assume true; {304#true} is VALID [2022-04-28 05:22:50,472 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {304#true} {309#(= ~counter~0 0)} #64#return; {309#(= ~counter~0 0)} is VALID [2022-04-28 05:22:50,473 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-28 05:22:50,475 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 05:22:50,478 INFO L290 TraceCheckUtils]: 0: Hoare triple {304#true} ~cond := #in~cond; {304#true} is VALID [2022-04-28 05:22:50,478 INFO L290 TraceCheckUtils]: 1: Hoare triple {304#true} assume !(0 == ~cond); {304#true} is VALID [2022-04-28 05:22:50,478 INFO L290 TraceCheckUtils]: 2: Hoare triple {304#true} assume true; {304#true} is VALID [2022-04-28 05:22:50,479 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {304#true} {309#(= ~counter~0 0)} #66#return; {309#(= ~counter~0 0)} is VALID [2022-04-28 05:22:50,480 INFO L272 TraceCheckUtils]: 0: Hoare triple {304#true} call ULTIMATE.init(); {319#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-28 05:22:50,480 INFO L290 TraceCheckUtils]: 1: Hoare triple {319#(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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {309#(= ~counter~0 0)} is VALID [2022-04-28 05:22:50,480 INFO L290 TraceCheckUtils]: 2: Hoare triple {309#(= ~counter~0 0)} assume true; {309#(= ~counter~0 0)} is VALID [2022-04-28 05:22:50,481 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {309#(= ~counter~0 0)} {304#true} #82#return; {309#(= ~counter~0 0)} is VALID [2022-04-28 05:22:50,481 INFO L272 TraceCheckUtils]: 4: Hoare triple {309#(= ~counter~0 0)} call #t~ret7 := main(); {309#(= ~counter~0 0)} is VALID [2022-04-28 05:22:50,481 INFO L290 TraceCheckUtils]: 5: Hoare triple {309#(= ~counter~0 0)} havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~s~0;havoc ~x~0;havoc ~y~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; {309#(= ~counter~0 0)} is VALID [2022-04-28 05:22:50,482 INFO L272 TraceCheckUtils]: 6: Hoare triple {309#(= ~counter~0 0)} call assume_abort_if_not((if ~x~0 >= 1 then 1 else 0)); {304#true} is VALID [2022-04-28 05:22:50,482 INFO L290 TraceCheckUtils]: 7: Hoare triple {304#true} ~cond := #in~cond; {304#true} is VALID [2022-04-28 05:22:50,482 INFO L290 TraceCheckUtils]: 8: Hoare triple {304#true} assume !(0 == ~cond); {304#true} is VALID [2022-04-28 05:22:50,482 INFO L290 TraceCheckUtils]: 9: Hoare triple {304#true} assume true; {304#true} is VALID [2022-04-28 05:22:50,482 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {304#true} {309#(= ~counter~0 0)} #64#return; {309#(= ~counter~0 0)} is VALID [2022-04-28 05:22:50,483 INFO L272 TraceCheckUtils]: 11: Hoare triple {309#(= ~counter~0 0)} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {304#true} is VALID [2022-04-28 05:22:50,483 INFO L290 TraceCheckUtils]: 12: Hoare triple {304#true} ~cond := #in~cond; {304#true} is VALID [2022-04-28 05:22:50,483 INFO L290 TraceCheckUtils]: 13: Hoare triple {304#true} assume !(0 == ~cond); {304#true} is VALID [2022-04-28 05:22:50,483 INFO L290 TraceCheckUtils]: 14: Hoare triple {304#true} assume true; {304#true} is VALID [2022-04-28 05:22:50,483 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {304#true} {309#(= ~counter~0 0)} #66#return; {309#(= ~counter~0 0)} is VALID [2022-04-28 05:22:50,484 INFO L290 TraceCheckUtils]: 16: Hoare triple {309#(= ~counter~0 0)} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0;~r~0 := 0;~s~0 := 1; {309#(= ~counter~0 0)} is VALID [2022-04-28 05:22:50,484 INFO L290 TraceCheckUtils]: 17: Hoare triple {309#(= ~counter~0 0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {318#(= |main_#t~post6| 0)} is VALID [2022-04-28 05:22:50,485 INFO L290 TraceCheckUtils]: 18: Hoare triple {318#(= |main_#t~post6| 0)} assume !(#t~post6 < 1);havoc #t~post6; {305#false} is VALID [2022-04-28 05:22:50,485 INFO L272 TraceCheckUtils]: 19: Hoare triple {305#false} call __VERIFIER_assert((if 0 == ~a~0 - ~b~0 then 1 else 0)); {305#false} is VALID [2022-04-28 05:22:50,485 INFO L290 TraceCheckUtils]: 20: Hoare triple {305#false} ~cond := #in~cond; {305#false} is VALID [2022-04-28 05:22:50,485 INFO L290 TraceCheckUtils]: 21: Hoare triple {305#false} assume 0 == ~cond; {305#false} is VALID [2022-04-28 05:22:50,485 INFO L290 TraceCheckUtils]: 22: Hoare triple {305#false} assume !false; {305#false} is VALID [2022-04-28 05:22:50,485 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-28 05:22:50,486 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 05:22:50,486 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1765271716] [2022-04-28 05:22:50,486 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1765271716] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 05:22:50,486 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 05:22:50,486 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 05:22:50,486 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 05:22:50,486 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1667143280] [2022-04-28 05:22:50,486 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1667143280] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 05:22:50,487 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 05:22:50,487 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 05:22:50,487 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [179799961] [2022-04-28 05:22:50,487 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 05:22:50,488 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), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-04-28 05:22:50,488 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 05:22:50,488 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), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 05:22:50,502 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 20 edges. 20 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:50,502 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 05:22:50,502 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 05:22:50,503 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 05:22:50,503 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-28 05:22:50,503 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 05:22:50,675 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:50,675 INFO L93 Difference]: Finished difference Result 42 states and 54 transitions. [2022-04-28 05:22:50,676 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-28 05:22:50,676 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), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-04-28 05:22:50,676 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 05:22:50,676 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), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 05:22:50,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 54 transitions. [2022-04-28 05:22:50,679 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), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 05:22:50,681 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 54 transitions. [2022-04-28 05:22:50,681 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 54 transitions. [2022-04-28 05:22:50,725 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 54 edges. 54 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:50,726 INFO L225 Difference]: With dead ends: 42 [2022-04-28 05:22:50,727 INFO L226 Difference]: Without dead ends: 32 [2022-04-28 05:22:50,727 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 8 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-28 05:22:50,728 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 13 mSDsluCounter, 30 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 65 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-28 05:22:50,728 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 65 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-28 05:22:50,729 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-28 05:22:50,733 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-04-28 05:22:50,733 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 05:22:50,733 INFO L82 GeneralOperation]: Start isEquivalent. First operand 32 states. Second operand has 32 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-28 05:22:50,734 INFO L74 IsIncluded]: Start isIncluded. First operand 32 states. Second operand has 32 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-28 05:22:50,734 INFO L87 Difference]: Start difference. First operand 32 states. Second operand has 32 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-28 05:22:50,736 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:50,736 INFO L93 Difference]: Finished difference Result 32 states and 41 transitions. [2022-04-28 05:22:50,736 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-04-28 05:22:50,737 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 05:22:50,737 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 05:22:50,737 INFO L74 IsIncluded]: Start isIncluded. First operand has 32 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 32 states. [2022-04-28 05:22:50,738 INFO L87 Difference]: Start difference. First operand has 32 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 32 states. [2022-04-28 05:22:50,739 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:50,740 INFO L93 Difference]: Finished difference Result 32 states and 41 transitions. [2022-04-28 05:22:50,740 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-04-28 05:22:50,740 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 05:22:50,740 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 05:22:50,740 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 05:22:50,740 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 05:22:50,741 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-28 05:22:50,742 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 41 transitions. [2022-04-28 05:22:50,742 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 41 transitions. Word has length 23 [2022-04-28 05:22:50,743 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 05:22:50,743 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 41 transitions. [2022-04-28 05:22:50,743 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 3 states have call successors, (5), 4 states have call predecessors, (5), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 05:22:50,743 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 32 states and 41 transitions. [2022-04-28 05:22:50,780 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 41 edges. 41 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:50,781 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 41 transitions. [2022-04-28 05:22:50,782 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-28 05:22:50,782 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 05:22:50,782 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 05:22:50,783 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-28 05:22:50,785 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 05:22:50,787 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 05:22:50,787 INFO L85 PathProgramCache]: Analyzing trace with hash 1348211113, now seen corresponding path program 1 times [2022-04-28 05:22:50,787 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 05:22:50,788 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [933690811] [2022-04-28 05:22:50,789 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 05:22:50,789 INFO L85 PathProgramCache]: Analyzing trace with hash 1348211113, now seen corresponding path program 2 times [2022-04-28 05:22:50,789 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 05:22:50,790 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [363724179] [2022-04-28 05:22:50,790 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 05:22:50,790 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 05:22:50,821 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 05:22:50,821 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1631293442] [2022-04-28 05:22:50,821 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 05:22:50,822 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 05:22:50,822 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 05:22:50,827 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-28 05:22:50,830 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-28 05:22:50,890 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-28 05:22:50,891 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-28 05:22:50,907 INFO L263 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-28 05:22:50,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 05:22:50,925 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 05:22:53,620 INFO L272 TraceCheckUtils]: 0: Hoare triple {537#true} call ULTIMATE.init(); {537#true} is VALID [2022-04-28 05:22:53,620 INFO L290 TraceCheckUtils]: 1: Hoare triple {537#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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {537#true} is VALID [2022-04-28 05:22:53,620 INFO L290 TraceCheckUtils]: 2: Hoare triple {537#true} assume true; {537#true} is VALID [2022-04-28 05:22:53,620 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {537#true} {537#true} #82#return; {537#true} is VALID [2022-04-28 05:22:53,620 INFO L272 TraceCheckUtils]: 4: Hoare triple {537#true} call #t~ret7 := main(); {537#true} is VALID [2022-04-28 05:22:53,621 INFO L290 TraceCheckUtils]: 5: Hoare triple {537#true} havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~s~0;havoc ~x~0;havoc ~y~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; {537#true} is VALID [2022-04-28 05:22:53,621 INFO L272 TraceCheckUtils]: 6: Hoare triple {537#true} call assume_abort_if_not((if ~x~0 >= 1 then 1 else 0)); {537#true} is VALID [2022-04-28 05:22:53,621 INFO L290 TraceCheckUtils]: 7: Hoare triple {537#true} ~cond := #in~cond; {537#true} is VALID [2022-04-28 05:22:53,621 INFO L290 TraceCheckUtils]: 8: Hoare triple {537#true} assume !(0 == ~cond); {537#true} is VALID [2022-04-28 05:22:53,621 INFO L290 TraceCheckUtils]: 9: Hoare triple {537#true} assume true; {537#true} is VALID [2022-04-28 05:22:53,621 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {537#true} {537#true} #64#return; {537#true} is VALID [2022-04-28 05:22:53,621 INFO L272 TraceCheckUtils]: 11: Hoare triple {537#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {537#true} is VALID [2022-04-28 05:22:53,621 INFO L290 TraceCheckUtils]: 12: Hoare triple {537#true} ~cond := #in~cond; {537#true} is VALID [2022-04-28 05:22:53,621 INFO L290 TraceCheckUtils]: 13: Hoare triple {537#true} assume !(0 == ~cond); {537#true} is VALID [2022-04-28 05:22:53,622 INFO L290 TraceCheckUtils]: 14: Hoare triple {537#true} assume true; {537#true} is VALID [2022-04-28 05:22:53,622 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {537#true} {537#true} #66#return; {537#true} is VALID [2022-04-28 05:22:53,622 INFO L290 TraceCheckUtils]: 16: Hoare triple {537#true} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0;~r~0 := 0;~s~0 := 1; {590#(and (= main_~r~0 0) (= main_~s~0 1) (= main_~p~0 1))} is VALID [2022-04-28 05:22:53,623 INFO L290 TraceCheckUtils]: 17: Hoare triple {590#(and (= main_~r~0 0) (= main_~s~0 1) (= main_~p~0 1))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {590#(and (= main_~r~0 0) (= main_~s~0 1) (= main_~p~0 1))} is VALID [2022-04-28 05:22:53,623 INFO L290 TraceCheckUtils]: 18: Hoare triple {590#(and (= main_~r~0 0) (= main_~s~0 1) (= main_~p~0 1))} assume !!(#t~post6 < 1);havoc #t~post6; {590#(and (= main_~r~0 0) (= main_~s~0 1) (= main_~p~0 1))} is VALID [2022-04-28 05:22:53,624 INFO L272 TraceCheckUtils]: 19: Hoare triple {590#(and (= main_~r~0 0) (= main_~s~0 1) (= main_~p~0 1))} call __VERIFIER_assert((if 1 == ~p~0 * ~s~0 - ~r~0 * ~q~0 then 1 else 0)); {600#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-28 05:22:53,625 INFO L290 TraceCheckUtils]: 20: Hoare triple {600#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {604#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 05:22:53,625 INFO L290 TraceCheckUtils]: 21: Hoare triple {604#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {538#false} is VALID [2022-04-28 05:22:53,626 INFO L290 TraceCheckUtils]: 22: Hoare triple {538#false} assume !false; {538#false} is VALID [2022-04-28 05:22:53,626 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-28 05:22:53,626 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-28 05:22:53,626 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 05:22:53,626 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [363724179] [2022-04-28 05:22:53,626 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 05:22:53,626 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1631293442] [2022-04-28 05:22:53,627 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1631293442] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 05:22:53,627 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 05:22:53,627 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 05:22:53,627 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 05:22:53,627 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [933690811] [2022-04-28 05:22:53,627 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [933690811] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 05:22:53,627 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 05:22:53,628 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 05:22:53,628 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [37993357] [2022-04-28 05:22:53,628 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 05:22:53,628 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 23 [2022-04-28 05:22:53,628 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 05:22:53,628 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 05:22:53,645 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 20 edges. 20 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:53,645 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 05:22:53,645 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 05:22:53,645 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 05:22:53,645 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-28 05:22:53,646 INFO L87 Difference]: Start difference. First operand 32 states and 41 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 05:22:53,810 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:53,810 INFO L93 Difference]: Finished difference Result 49 states and 66 transitions. [2022-04-28 05:22:53,810 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-28 05:22:53,811 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 23 [2022-04-28 05:22:53,811 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 05:22:53,811 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 05:22:53,813 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 64 transitions. [2022-04-28 05:22:53,813 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 05:22:53,835 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 64 transitions. [2022-04-28 05:22:53,835 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 64 transitions. [2022-04-28 05:22:53,901 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 64 edges. 64 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:53,903 INFO L225 Difference]: With dead ends: 49 [2022-04-28 05:22:53,903 INFO L226 Difference]: Without dead ends: 47 [2022-04-28 05:22:53,903 INFO L412 NwaCegarLoop]: 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-28 05:22:53,904 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 8 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-28 05:22:53,904 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 136 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-28 05:22:53,905 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2022-04-28 05:22:53,928 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2022-04-28 05:22:53,928 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 05:22:53,929 INFO L82 GeneralOperation]: Start isEquivalent. First operand 47 states. Second operand has 46 states, 24 states have (on average 1.2916666666666667) internal successors, (31), 26 states have internal predecessors, (31), 17 states have call successors, (17), 5 states have call predecessors, (17), 4 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-28 05:22:53,929 INFO L74 IsIncluded]: Start isIncluded. First operand 47 states. Second operand has 46 states, 24 states have (on average 1.2916666666666667) internal successors, (31), 26 states have internal predecessors, (31), 17 states have call successors, (17), 5 states have call predecessors, (17), 4 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-28 05:22:53,929 INFO L87 Difference]: Start difference. First operand 47 states. Second operand has 46 states, 24 states have (on average 1.2916666666666667) internal successors, (31), 26 states have internal predecessors, (31), 17 states have call successors, (17), 5 states have call predecessors, (17), 4 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-28 05:22:53,932 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:53,932 INFO L93 Difference]: Finished difference Result 47 states and 64 transitions. [2022-04-28 05:22:53,932 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 64 transitions. [2022-04-28 05:22:53,932 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 05:22:53,933 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 05:22:53,933 INFO L74 IsIncluded]: Start isIncluded. First operand has 46 states, 24 states have (on average 1.2916666666666667) internal successors, (31), 26 states have internal predecessors, (31), 17 states have call successors, (17), 5 states have call predecessors, (17), 4 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) Second operand 47 states. [2022-04-28 05:22:53,933 INFO L87 Difference]: Start difference. First operand has 46 states, 24 states have (on average 1.2916666666666667) internal successors, (31), 26 states have internal predecessors, (31), 17 states have call successors, (17), 5 states have call predecessors, (17), 4 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) Second operand 47 states. [2022-04-28 05:22:53,935 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:53,936 INFO L93 Difference]: Finished difference Result 47 states and 64 transitions. [2022-04-28 05:22:53,936 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 64 transitions. [2022-04-28 05:22:53,936 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 05:22:53,936 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 05:22:53,936 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 05:22:53,937 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 05:22:53,937 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 24 states have (on average 1.2916666666666667) internal successors, (31), 26 states have internal predecessors, (31), 17 states have call successors, (17), 5 states have call predecessors, (17), 4 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-28 05:22:53,939 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 63 transitions. [2022-04-28 05:22:53,939 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 63 transitions. Word has length 23 [2022-04-28 05:22:53,939 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 05:22:53,939 INFO L495 AbstractCegarLoop]: Abstraction has 46 states and 63 transitions. [2022-04-28 05:22:53,939 INFO L496 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, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 05:22:53,939 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 46 states and 63 transitions. [2022-04-28 05:22:53,991 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 63 edges. 63 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:53,991 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 63 transitions. [2022-04-28 05:22:53,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-28 05:22:53,992 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 05:22:53,992 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 05:22:54,032 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-28 05:22:54,207 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 05:22:54,208 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 05:22:54,208 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 05:22:54,208 INFO L85 PathProgramCache]: Analyzing trace with hash -1060153012, now seen corresponding path program 1 times [2022-04-28 05:22:54,208 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 05:22:54,209 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1350830637] [2022-04-28 05:22:54,209 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 05:22:54,209 INFO L85 PathProgramCache]: Analyzing trace with hash -1060153012, now seen corresponding path program 2 times [2022-04-28 05:22:54,209 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 05:22:54,209 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1481164525] [2022-04-28 05:22:54,210 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 05:22:54,210 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 05:22:54,221 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 05:22:54,221 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2084332368] [2022-04-28 05:22:54,221 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 05:22:54,221 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 05:22:54,221 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 05:22:54,222 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-28 05:22:54,223 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-28 05:22:54,257 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-28 05:22:54,258 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-28 05:22:54,259 INFO L263 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-28 05:22:54,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 05:22:54,267 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 05:22:58,384 INFO L272 TraceCheckUtils]: 0: Hoare triple {896#true} call ULTIMATE.init(); {896#true} is VALID [2022-04-28 05:22:58,385 INFO L290 TraceCheckUtils]: 1: Hoare triple {896#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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {896#true} is VALID [2022-04-28 05:22:58,385 INFO L290 TraceCheckUtils]: 2: Hoare triple {896#true} assume true; {896#true} is VALID [2022-04-28 05:22:58,385 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {896#true} {896#true} #82#return; {896#true} is VALID [2022-04-28 05:22:58,385 INFO L272 TraceCheckUtils]: 4: Hoare triple {896#true} call #t~ret7 := main(); {896#true} is VALID [2022-04-28 05:22:58,385 INFO L290 TraceCheckUtils]: 5: Hoare triple {896#true} havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~s~0;havoc ~x~0;havoc ~y~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; {896#true} is VALID [2022-04-28 05:22:58,385 INFO L272 TraceCheckUtils]: 6: Hoare triple {896#true} call assume_abort_if_not((if ~x~0 >= 1 then 1 else 0)); {896#true} is VALID [2022-04-28 05:22:58,385 INFO L290 TraceCheckUtils]: 7: Hoare triple {896#true} ~cond := #in~cond; {896#true} is VALID [2022-04-28 05:22:58,386 INFO L290 TraceCheckUtils]: 8: Hoare triple {896#true} assume !(0 == ~cond); {896#true} is VALID [2022-04-28 05:22:58,386 INFO L290 TraceCheckUtils]: 9: Hoare triple {896#true} assume true; {896#true} is VALID [2022-04-28 05:22:58,386 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {896#true} {896#true} #64#return; {896#true} is VALID [2022-04-28 05:22:58,386 INFO L272 TraceCheckUtils]: 11: Hoare triple {896#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {896#true} is VALID [2022-04-28 05:22:58,386 INFO L290 TraceCheckUtils]: 12: Hoare triple {896#true} ~cond := #in~cond; {896#true} is VALID [2022-04-28 05:22:58,386 INFO L290 TraceCheckUtils]: 13: Hoare triple {896#true} assume !(0 == ~cond); {896#true} is VALID [2022-04-28 05:22:58,386 INFO L290 TraceCheckUtils]: 14: Hoare triple {896#true} assume true; {896#true} is VALID [2022-04-28 05:22:58,386 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {896#true} {896#true} #66#return; {896#true} is VALID [2022-04-28 05:22:58,388 INFO L290 TraceCheckUtils]: 16: Hoare triple {896#true} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0;~r~0 := 0;~s~0 := 1; {949#(and (= main_~r~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-28 05:22:58,388 INFO L290 TraceCheckUtils]: 17: Hoare triple {949#(and (= main_~r~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {949#(and (= main_~r~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-28 05:22:58,389 INFO L290 TraceCheckUtils]: 18: Hoare triple {949#(and (= main_~r~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} assume !!(#t~post6 < 1);havoc #t~post6; {949#(and (= main_~r~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-28 05:22:58,389 INFO L272 TraceCheckUtils]: 19: Hoare triple {949#(and (= main_~r~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} call __VERIFIER_assert((if 1 == ~p~0 * ~s~0 - ~r~0 * ~q~0 then 1 else 0)); {896#true} is VALID [2022-04-28 05:22:58,389 INFO L290 TraceCheckUtils]: 20: Hoare triple {896#true} ~cond := #in~cond; {896#true} is VALID [2022-04-28 05:22:58,389 INFO L290 TraceCheckUtils]: 21: Hoare triple {896#true} assume !(0 == ~cond); {896#true} is VALID [2022-04-28 05:22:58,389 INFO L290 TraceCheckUtils]: 22: Hoare triple {896#true} assume true; {896#true} is VALID [2022-04-28 05:22:58,390 INFO L284 TraceCheckUtils]: 23: Hoare quadruple {896#true} {949#(and (= main_~r~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} #68#return; {949#(and (= main_~r~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} is VALID [2022-04-28 05:22:58,391 INFO L272 TraceCheckUtils]: 24: Hoare triple {949#(and (= main_~r~0 0) (= main_~a~0 main_~x~0) (= main_~p~0 1))} call __VERIFIER_assert((if ~a~0 == ~y~0 * ~r~0 + ~x~0 * ~p~0 then 1 else 0)); {974#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-28 05:22:58,391 INFO L290 TraceCheckUtils]: 25: Hoare triple {974#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {978#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 05:22:58,391 INFO L290 TraceCheckUtils]: 26: Hoare triple {978#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {897#false} is VALID [2022-04-28 05:22:58,392 INFO L290 TraceCheckUtils]: 27: Hoare triple {897#false} assume !false; {897#false} is VALID [2022-04-28 05:22:58,392 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-28 05:22:58,392 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-28 05:22:58,392 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 05:22:58,392 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1481164525] [2022-04-28 05:22:58,392 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 05:22:58,393 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2084332368] [2022-04-28 05:22:58,393 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2084332368] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 05:22:58,393 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 05:22:58,393 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 05:22:58,393 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 05:22:58,393 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1350830637] [2022-04-28 05:22:58,393 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1350830637] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 05:22:58,393 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 05:22:58,393 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 05:22:58,393 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [528939791] [2022-04-28 05:22:58,394 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 05:22:58,394 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-28 05:22:58,394 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 05:22:58,394 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-28 05:22:58,412 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 25 edges. 25 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:58,412 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 05:22:58,412 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 05:22:58,413 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 05:22:58,413 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-28 05:22:58,413 INFO L87 Difference]: Start difference. First operand 46 states and 63 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-28 05:22:58,597 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:58,597 INFO L93 Difference]: Finished difference Result 53 states and 69 transitions. [2022-04-28 05:22:58,597 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-28 05:22:58,597 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-28 05:22:58,598 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 05:22:58,598 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-28 05:22:58,599 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 64 transitions. [2022-04-28 05:22:58,599 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-28 05:22:58,600 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 64 transitions. [2022-04-28 05:22:58,600 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 64 transitions. [2022-04-28 05:22:58,647 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 64 edges. 64 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:58,649 INFO L225 Difference]: With dead ends: 53 [2022-04-28 05:22:58,649 INFO L226 Difference]: Without dead ends: 51 [2022-04-28 05:22:58,649 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 24 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-28 05:22:58,653 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 9 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-28 05:22:58,653 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 136 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-28 05:22:58,654 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-04-28 05:22:58,664 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 50. [2022-04-28 05:22:58,665 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 05:22:58,665 INFO L82 GeneralOperation]: Start isEquivalent. First operand 51 states. Second operand has 50 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 17 states have call successors, (17), 6 states have call predecessors, (17), 5 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-28 05:22:58,665 INFO L74 IsIncluded]: Start isIncluded. First operand 51 states. Second operand has 50 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 17 states have call successors, (17), 6 states have call predecessors, (17), 5 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-28 05:22:58,666 INFO L87 Difference]: Start difference. First operand 51 states. Second operand has 50 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 17 states have call successors, (17), 6 states have call predecessors, (17), 5 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-28 05:22:58,667 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:58,668 INFO L93 Difference]: Finished difference Result 51 states and 67 transitions. [2022-04-28 05:22:58,668 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 67 transitions. [2022-04-28 05:22:58,668 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 05:22:58,668 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 05:22:58,668 INFO L74 IsIncluded]: Start isIncluded. First operand has 50 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 17 states have call successors, (17), 6 states have call predecessors, (17), 5 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) Second operand 51 states. [2022-04-28 05:22:58,669 INFO L87 Difference]: Start difference. First operand has 50 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 17 states have call successors, (17), 6 states have call predecessors, (17), 5 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) Second operand 51 states. [2022-04-28 05:22:58,671 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:58,671 INFO L93 Difference]: Finished difference Result 51 states and 67 transitions. [2022-04-28 05:22:58,671 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 67 transitions. [2022-04-28 05:22:58,671 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 05:22:58,671 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 05:22:58,671 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 05:22:58,671 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 05:22:58,672 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 29 states have internal predecessors, (34), 17 states have call successors, (17), 6 states have call predecessors, (17), 5 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-28 05:22:58,673 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 66 transitions. [2022-04-28 05:22:58,673 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 66 transitions. Word has length 28 [2022-04-28 05:22:58,673 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 05:22:58,674 INFO L495 AbstractCegarLoop]: Abstraction has 50 states and 66 transitions. [2022-04-28 05:22:58,674 INFO L496 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, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-28 05:22:58,674 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 50 states and 66 transitions. [2022-04-28 05:22:58,745 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 66 edges. 66 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:58,745 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 66 transitions. [2022-04-28 05:22:58,746 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-04-28 05:22:58,746 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 05:22:58,746 INFO L195 NwaCegarLoop]: 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] [2022-04-28 05:22:58,765 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-28 05:22:58,951 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2022-04-28 05:22:58,952 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 05:22:58,952 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 05:22:58,952 INFO L85 PathProgramCache]: Analyzing trace with hash -560761015, now seen corresponding path program 1 times [2022-04-28 05:22:58,952 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 05:22:58,952 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [272788709] [2022-04-28 05:22:58,953 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 05:22:58,953 INFO L85 PathProgramCache]: Analyzing trace with hash -560761015, now seen corresponding path program 2 times [2022-04-28 05:22:58,953 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 05:22:58,953 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [556311507] [2022-04-28 05:22:58,953 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 05:22:58,953 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 05:22:58,963 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 05:22:58,964 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1798560025] [2022-04-28 05:22:58,964 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 05:22:58,964 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 05:22:58,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 05:22:58,976 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-28 05:22:58,977 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-28 05:22:59,011 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-28 05:22:59,011 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-28 05:22:59,012 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-28 05:22:59,024 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 05:22:59,025 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 05:22:59,176 INFO L272 TraceCheckUtils]: 0: Hoare triple {1294#true} call ULTIMATE.init(); {1294#true} is VALID [2022-04-28 05:22:59,177 INFO L290 TraceCheckUtils]: 1: Hoare triple {1294#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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1294#true} is VALID [2022-04-28 05:22:59,177 INFO L290 TraceCheckUtils]: 2: Hoare triple {1294#true} assume true; {1294#true} is VALID [2022-04-28 05:22:59,177 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1294#true} {1294#true} #82#return; {1294#true} is VALID [2022-04-28 05:22:59,177 INFO L272 TraceCheckUtils]: 4: Hoare triple {1294#true} call #t~ret7 := main(); {1294#true} is VALID [2022-04-28 05:22:59,177 INFO L290 TraceCheckUtils]: 5: Hoare triple {1294#true} havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~s~0;havoc ~x~0;havoc ~y~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; {1294#true} is VALID [2022-04-28 05:22:59,177 INFO L272 TraceCheckUtils]: 6: Hoare triple {1294#true} call assume_abort_if_not((if ~x~0 >= 1 then 1 else 0)); {1294#true} is VALID [2022-04-28 05:22:59,179 INFO L290 TraceCheckUtils]: 7: Hoare triple {1294#true} ~cond := #in~cond; {1320#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-28 05:22:59,179 INFO L290 TraceCheckUtils]: 8: Hoare triple {1320#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {1324#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-28 05:22:59,180 INFO L290 TraceCheckUtils]: 9: Hoare triple {1324#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {1324#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-28 05:22:59,180 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1324#(not (= |assume_abort_if_not_#in~cond| 0))} {1294#true} #64#return; {1331#(<= 1 main_~x~0)} is VALID [2022-04-28 05:22:59,180 INFO L272 TraceCheckUtils]: 11: Hoare triple {1331#(<= 1 main_~x~0)} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1294#true} is VALID [2022-04-28 05:22:59,180 INFO L290 TraceCheckUtils]: 12: Hoare triple {1294#true} ~cond := #in~cond; {1294#true} is VALID [2022-04-28 05:22:59,180 INFO L290 TraceCheckUtils]: 13: Hoare triple {1294#true} assume !(0 == ~cond); {1294#true} is VALID [2022-04-28 05:22:59,181 INFO L290 TraceCheckUtils]: 14: Hoare triple {1294#true} assume true; {1294#true} is VALID [2022-04-28 05:22:59,191 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {1294#true} {1331#(<= 1 main_~x~0)} #66#return; {1331#(<= 1 main_~x~0)} is VALID [2022-04-28 05:22:59,191 INFO L290 TraceCheckUtils]: 16: Hoare triple {1331#(<= 1 main_~x~0)} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0;~r~0 := 0;~s~0 := 1; {1350#(and (<= 1 main_~x~0) (= main_~s~0 1) (= main_~b~0 main_~y~0) (= main_~q~0 0))} is VALID [2022-04-28 05:22:59,192 INFO L290 TraceCheckUtils]: 17: Hoare triple {1350#(and (<= 1 main_~x~0) (= main_~s~0 1) (= main_~b~0 main_~y~0) (= main_~q~0 0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1350#(and (<= 1 main_~x~0) (= main_~s~0 1) (= main_~b~0 main_~y~0) (= main_~q~0 0))} is VALID [2022-04-28 05:22:59,192 INFO L290 TraceCheckUtils]: 18: Hoare triple {1350#(and (<= 1 main_~x~0) (= main_~s~0 1) (= main_~b~0 main_~y~0) (= main_~q~0 0))} assume !!(#t~post6 < 1);havoc #t~post6; {1350#(and (<= 1 main_~x~0) (= main_~s~0 1) (= main_~b~0 main_~y~0) (= main_~q~0 0))} is VALID [2022-04-28 05:22:59,192 INFO L272 TraceCheckUtils]: 19: Hoare triple {1350#(and (<= 1 main_~x~0) (= main_~s~0 1) (= main_~b~0 main_~y~0) (= main_~q~0 0))} call __VERIFIER_assert((if 1 == ~p~0 * ~s~0 - ~r~0 * ~q~0 then 1 else 0)); {1294#true} is VALID [2022-04-28 05:22:59,192 INFO L290 TraceCheckUtils]: 20: Hoare triple {1294#true} ~cond := #in~cond; {1294#true} is VALID [2022-04-28 05:22:59,192 INFO L290 TraceCheckUtils]: 21: Hoare triple {1294#true} assume !(0 == ~cond); {1294#true} is VALID [2022-04-28 05:22:59,192 INFO L290 TraceCheckUtils]: 22: Hoare triple {1294#true} assume true; {1294#true} is VALID [2022-04-28 05:22:59,193 INFO L284 TraceCheckUtils]: 23: Hoare quadruple {1294#true} {1350#(and (<= 1 main_~x~0) (= main_~s~0 1) (= main_~b~0 main_~y~0) (= main_~q~0 0))} #68#return; {1350#(and (<= 1 main_~x~0) (= main_~s~0 1) (= main_~b~0 main_~y~0) (= main_~q~0 0))} is VALID [2022-04-28 05:22:59,193 INFO L272 TraceCheckUtils]: 24: Hoare triple {1350#(and (<= 1 main_~x~0) (= main_~s~0 1) (= main_~b~0 main_~y~0) (= main_~q~0 0))} call __VERIFIER_assert((if ~a~0 == ~y~0 * ~r~0 + ~x~0 * ~p~0 then 1 else 0)); {1294#true} is VALID [2022-04-28 05:22:59,193 INFO L290 TraceCheckUtils]: 25: Hoare triple {1294#true} ~cond := #in~cond; {1294#true} is VALID [2022-04-28 05:22:59,193 INFO L290 TraceCheckUtils]: 26: Hoare triple {1294#true} assume !(0 == ~cond); {1294#true} is VALID [2022-04-28 05:22:59,193 INFO L290 TraceCheckUtils]: 27: Hoare triple {1294#true} assume true; {1294#true} is VALID [2022-04-28 05:22:59,194 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {1294#true} {1350#(and (<= 1 main_~x~0) (= main_~s~0 1) (= main_~b~0 main_~y~0) (= main_~q~0 0))} #70#return; {1350#(and (<= 1 main_~x~0) (= main_~s~0 1) (= main_~b~0 main_~y~0) (= main_~q~0 0))} is VALID [2022-04-28 05:22:59,195 INFO L272 TraceCheckUtils]: 29: Hoare triple {1350#(and (<= 1 main_~x~0) (= main_~s~0 1) (= main_~b~0 main_~y~0) (= main_~q~0 0))} call __VERIFIER_assert((if ~b~0 == ~x~0 * ~q~0 + ~y~0 * ~s~0 then 1 else 0)); {1390#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-28 05:22:59,195 INFO L290 TraceCheckUtils]: 30: Hoare triple {1390#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1394#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 05:22:59,195 INFO L290 TraceCheckUtils]: 31: Hoare triple {1394#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1295#false} is VALID [2022-04-28 05:22:59,195 INFO L290 TraceCheckUtils]: 32: Hoare triple {1295#false} assume !false; {1295#false} is VALID [2022-04-28 05:22:59,196 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-04-28 05:22:59,196 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-28 05:22:59,341 INFO L290 TraceCheckUtils]: 32: Hoare triple {1295#false} assume !false; {1295#false} is VALID [2022-04-28 05:22:59,341 INFO L290 TraceCheckUtils]: 31: Hoare triple {1394#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1295#false} is VALID [2022-04-28 05:22:59,341 INFO L290 TraceCheckUtils]: 30: Hoare triple {1390#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1394#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 05:22:59,342 INFO L272 TraceCheckUtils]: 29: Hoare triple {1410#(= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0)))} call __VERIFIER_assert((if ~b~0 == ~x~0 * ~q~0 + ~y~0 * ~s~0 then 1 else 0)); {1390#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-28 05:22:59,343 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {1294#true} {1410#(= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0)))} #70#return; {1410#(= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0)))} is VALID [2022-04-28 05:22:59,343 INFO L290 TraceCheckUtils]: 27: Hoare triple {1294#true} assume true; {1294#true} is VALID [2022-04-28 05:22:59,343 INFO L290 TraceCheckUtils]: 26: Hoare triple {1294#true} assume !(0 == ~cond); {1294#true} is VALID [2022-04-28 05:22:59,343 INFO L290 TraceCheckUtils]: 25: Hoare triple {1294#true} ~cond := #in~cond; {1294#true} is VALID [2022-04-28 05:22:59,343 INFO L272 TraceCheckUtils]: 24: Hoare triple {1410#(= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0)))} call __VERIFIER_assert((if ~a~0 == ~y~0 * ~r~0 + ~x~0 * ~p~0 then 1 else 0)); {1294#true} is VALID [2022-04-28 05:22:59,344 INFO L284 TraceCheckUtils]: 23: Hoare quadruple {1294#true} {1410#(= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0)))} #68#return; {1410#(= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0)))} is VALID [2022-04-28 05:22:59,344 INFO L290 TraceCheckUtils]: 22: Hoare triple {1294#true} assume true; {1294#true} is VALID [2022-04-28 05:22:59,344 INFO L290 TraceCheckUtils]: 21: Hoare triple {1294#true} assume !(0 == ~cond); {1294#true} is VALID [2022-04-28 05:22:59,344 INFO L290 TraceCheckUtils]: 20: Hoare triple {1294#true} ~cond := #in~cond; {1294#true} is VALID [2022-04-28 05:22:59,344 INFO L272 TraceCheckUtils]: 19: Hoare triple {1410#(= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0)))} call __VERIFIER_assert((if 1 == ~p~0 * ~s~0 - ~r~0 * ~q~0 then 1 else 0)); {1294#true} is VALID [2022-04-28 05:22:59,345 INFO L290 TraceCheckUtils]: 18: Hoare triple {1410#(= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0)))} assume !!(#t~post6 < 1);havoc #t~post6; {1410#(= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0)))} is VALID [2022-04-28 05:22:59,345 INFO L290 TraceCheckUtils]: 17: Hoare triple {1410#(= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0)))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1410#(= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0)))} is VALID [2022-04-28 05:22:59,345 INFO L290 TraceCheckUtils]: 16: Hoare triple {1294#true} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0;~r~0 := 0;~s~0 := 1; {1410#(= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0)))} is VALID [2022-04-28 05:22:59,345 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {1294#true} {1294#true} #66#return; {1294#true} is VALID [2022-04-28 05:22:59,346 INFO L290 TraceCheckUtils]: 14: Hoare triple {1294#true} assume true; {1294#true} is VALID [2022-04-28 05:22:59,346 INFO L290 TraceCheckUtils]: 13: Hoare triple {1294#true} assume !(0 == ~cond); {1294#true} is VALID [2022-04-28 05:22:59,346 INFO L290 TraceCheckUtils]: 12: Hoare triple {1294#true} ~cond := #in~cond; {1294#true} is VALID [2022-04-28 05:22:59,346 INFO L272 TraceCheckUtils]: 11: Hoare triple {1294#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1294#true} is VALID [2022-04-28 05:22:59,346 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1294#true} {1294#true} #64#return; {1294#true} is VALID [2022-04-28 05:22:59,346 INFO L290 TraceCheckUtils]: 9: Hoare triple {1294#true} assume true; {1294#true} is VALID [2022-04-28 05:22:59,346 INFO L290 TraceCheckUtils]: 8: Hoare triple {1294#true} assume !(0 == ~cond); {1294#true} is VALID [2022-04-28 05:22:59,346 INFO L290 TraceCheckUtils]: 7: Hoare triple {1294#true} ~cond := #in~cond; {1294#true} is VALID [2022-04-28 05:22:59,346 INFO L272 TraceCheckUtils]: 6: Hoare triple {1294#true} call assume_abort_if_not((if ~x~0 >= 1 then 1 else 0)); {1294#true} is VALID [2022-04-28 05:22:59,346 INFO L290 TraceCheckUtils]: 5: Hoare triple {1294#true} havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~s~0;havoc ~x~0;havoc ~y~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; {1294#true} is VALID [2022-04-28 05:22:59,347 INFO L272 TraceCheckUtils]: 4: Hoare triple {1294#true} call #t~ret7 := main(); {1294#true} is VALID [2022-04-28 05:22:59,347 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1294#true} {1294#true} #82#return; {1294#true} is VALID [2022-04-28 05:22:59,347 INFO L290 TraceCheckUtils]: 2: Hoare triple {1294#true} assume true; {1294#true} is VALID [2022-04-28 05:22:59,347 INFO L290 TraceCheckUtils]: 1: Hoare triple {1294#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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1294#true} is VALID [2022-04-28 05:22:59,347 INFO L272 TraceCheckUtils]: 0: Hoare triple {1294#true} call ULTIMATE.init(); {1294#true} is VALID [2022-04-28 05:22:59,347 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2022-04-28 05:22:59,347 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 05:22:59,347 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [556311507] [2022-04-28 05:22:59,347 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 05:22:59,348 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1798560025] [2022-04-28 05:22:59,348 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1798560025] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-28 05:22:59,348 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-28 05:22:59,348 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 9 [2022-04-28 05:22:59,348 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 05:22:59,348 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [272788709] [2022-04-28 05:22:59,348 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [272788709] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 05:22:59,348 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 05:22:59,348 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 05:22:59,348 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [461036460] [2022-04-28 05:22:59,348 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 05:22:59,349 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-04-28 05:22:59,349 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 05:22:59,349 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 05:22:59,365 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 27 edges. 27 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:59,365 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 05:22:59,365 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 05:22:59,365 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 05:22:59,367 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-04-28 05:22:59,367 INFO L87 Difference]: Start difference. First operand 50 states and 66 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 05:22:59,553 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:59,553 INFO L93 Difference]: Finished difference Result 75 states and 107 transitions. [2022-04-28 05:22:59,554 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-28 05:22:59,554 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-04-28 05:22:59,554 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 05:22:59,554 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 05:22:59,555 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 64 transitions. [2022-04-28 05:22:59,555 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 05:22:59,556 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 64 transitions. [2022-04-28 05:22:59,556 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 64 transitions. [2022-04-28 05:22:59,587 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 64 edges. 64 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:59,589 INFO L225 Difference]: With dead ends: 75 [2022-04-28 05:22:59,589 INFO L226 Difference]: Without dead ends: 71 [2022-04-28 05:22:59,589 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 57 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-04-28 05:22:59,590 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 9 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-28 05:22:59,590 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 128 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-28 05:22:59,590 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2022-04-28 05:22:59,635 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2022-04-28 05:22:59,635 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 05:22:59,635 INFO L82 GeneralOperation]: Start isEquivalent. First operand 71 states. Second operand has 71 states, 36 states have (on average 1.3333333333333333) internal successors, (48), 40 states have internal predecessors, (48), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-28 05:22:59,637 INFO L74 IsIncluded]: Start isIncluded. First operand 71 states. Second operand has 71 states, 36 states have (on average 1.3333333333333333) internal successors, (48), 40 states have internal predecessors, (48), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-28 05:22:59,637 INFO L87 Difference]: Start difference. First operand 71 states. Second operand has 71 states, 36 states have (on average 1.3333333333333333) internal successors, (48), 40 states have internal predecessors, (48), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-28 05:22:59,641 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:59,641 INFO L93 Difference]: Finished difference Result 71 states and 100 transitions. [2022-04-28 05:22:59,641 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 100 transitions. [2022-04-28 05:22:59,642 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 05:22:59,642 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 05:22:59,656 INFO L74 IsIncluded]: Start isIncluded. First operand has 71 states, 36 states have (on average 1.3333333333333333) internal successors, (48), 40 states have internal predecessors, (48), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) Second operand 71 states. [2022-04-28 05:22:59,657 INFO L87 Difference]: Start difference. First operand has 71 states, 36 states have (on average 1.3333333333333333) internal successors, (48), 40 states have internal predecessors, (48), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) Second operand 71 states. [2022-04-28 05:22:59,661 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:22:59,661 INFO L93 Difference]: Finished difference Result 71 states and 100 transitions. [2022-04-28 05:22:59,661 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 100 transitions. [2022-04-28 05:22:59,662 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 05:22:59,662 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 05:22:59,662 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 05:22:59,662 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 05:22:59,662 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 36 states have (on average 1.3333333333333333) internal successors, (48), 40 states have internal predecessors, (48), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-28 05:22:59,665 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 100 transitions. [2022-04-28 05:22:59,665 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 100 transitions. Word has length 33 [2022-04-28 05:22:59,665 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 05:22:59,665 INFO L495 AbstractCegarLoop]: Abstraction has 71 states and 100 transitions. [2022-04-28 05:22:59,665 INFO L496 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 05:22:59,665 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 71 states and 100 transitions. [2022-04-28 05:22:59,724 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 100 edges. 100 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:22:59,724 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 100 transitions. [2022-04-28 05:22:59,724 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-04-28 05:22:59,725 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 05:22:59,725 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 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] [2022-04-28 05:22:59,744 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-28 05:22:59,925 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 05:22:59,925 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 05:22:59,926 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 05:22:59,926 INFO L85 PathProgramCache]: Analyzing trace with hash 201438379, now seen corresponding path program 1 times [2022-04-28 05:22:59,926 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 05:22:59,926 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [588532860] [2022-04-28 05:22:59,926 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 05:22:59,926 INFO L85 PathProgramCache]: Analyzing trace with hash 201438379, now seen corresponding path program 2 times [2022-04-28 05:22:59,926 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 05:22:59,926 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1191902080] [2022-04-28 05:22:59,927 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 05:22:59,927 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 05:22:59,938 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 05:22:59,938 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [567400280] [2022-04-28 05:22:59,938 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 05:22:59,938 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 05:22:59,938 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 05:22:59,948 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-28 05:22:59,964 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-28 05:23:00,011 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-28 05:23:00,011 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-28 05:23:00,012 INFO L263 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-28 05:23:00,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 05:23:00,033 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 05:23:00,108 INFO L272 TraceCheckUtils]: 0: Hoare triple {1936#true} call ULTIMATE.init(); {1936#true} is VALID [2022-04-28 05:23:00,108 INFO L290 TraceCheckUtils]: 1: Hoare triple {1936#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(10, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1936#true} is VALID [2022-04-28 05:23:00,108 INFO L290 TraceCheckUtils]: 2: Hoare triple {1936#true} assume true; {1936#true} is VALID [2022-04-28 05:23:00,108 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1936#true} {1936#true} #82#return; {1936#true} is VALID [2022-04-28 05:23:00,108 INFO L272 TraceCheckUtils]: 4: Hoare triple {1936#true} call #t~ret7 := main(); {1936#true} is VALID [2022-04-28 05:23:00,108 INFO L290 TraceCheckUtils]: 5: Hoare triple {1936#true} havoc ~a~0;havoc ~b~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~s~0;havoc ~x~0;havoc ~y~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; {1936#true} is VALID [2022-04-28 05:23:00,108 INFO L272 TraceCheckUtils]: 6: Hoare triple {1936#true} call assume_abort_if_not((if ~x~0 >= 1 then 1 else 0)); {1936#true} is VALID [2022-04-28 05:23:00,108 INFO L290 TraceCheckUtils]: 7: Hoare triple {1936#true} ~cond := #in~cond; {1936#true} is VALID [2022-04-28 05:23:00,108 INFO L290 TraceCheckUtils]: 8: Hoare triple {1936#true} assume !(0 == ~cond); {1936#true} is VALID [2022-04-28 05:23:00,109 INFO L290 TraceCheckUtils]: 9: Hoare triple {1936#true} assume true; {1936#true} is VALID [2022-04-28 05:23:00,109 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1936#true} {1936#true} #64#return; {1936#true} is VALID [2022-04-28 05:23:00,109 INFO L272 TraceCheckUtils]: 11: Hoare triple {1936#true} call assume_abort_if_not((if ~y~0 >= 1 then 1 else 0)); {1936#true} is VALID [2022-04-28 05:23:00,109 INFO L290 TraceCheckUtils]: 12: Hoare triple {1936#true} ~cond := #in~cond; {1936#true} is VALID [2022-04-28 05:23:00,109 INFO L290 TraceCheckUtils]: 13: Hoare triple {1936#true} assume !(0 == ~cond); {1936#true} is VALID [2022-04-28 05:23:00,109 INFO L290 TraceCheckUtils]: 14: Hoare triple {1936#true} assume true; {1936#true} is VALID [2022-04-28 05:23:00,109 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {1936#true} {1936#true} #66#return; {1936#true} is VALID [2022-04-28 05:23:00,109 INFO L290 TraceCheckUtils]: 16: Hoare triple {1936#true} ~a~0 := ~x~0;~b~0 := ~y~0;~p~0 := 1;~q~0 := 0;~r~0 := 0;~s~0 := 1; {1936#true} is VALID [2022-04-28 05:23:00,109 INFO L290 TraceCheckUtils]: 17: Hoare triple {1936#true} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {1936#true} is VALID [2022-04-28 05:23:00,109 INFO L290 TraceCheckUtils]: 18: Hoare triple {1936#true} assume !!(#t~post6 < 1);havoc #t~post6; {1936#true} is VALID [2022-04-28 05:23:00,109 INFO L272 TraceCheckUtils]: 19: Hoare triple {1936#true} call __VERIFIER_assert((if 1 == ~p~0 * ~s~0 - ~r~0 * ~q~0 then 1 else 0)); {1936#true} is VALID [2022-04-28 05:23:00,109 INFO L290 TraceCheckUtils]: 20: Hoare triple {1936#true} ~cond := #in~cond; {1936#true} is VALID [2022-04-28 05:23:00,109 INFO L290 TraceCheckUtils]: 21: Hoare triple {1936#true} assume !(0 == ~cond); {1936#true} is VALID [2022-04-28 05:23:00,110 INFO L290 TraceCheckUtils]: 22: Hoare triple {1936#true} assume true; {1936#true} is VALID [2022-04-28 05:23:00,110 INFO L284 TraceCheckUtils]: 23: Hoare quadruple {1936#true} {1936#true} #68#return; {1936#true} is VALID [2022-04-28 05:23:00,110 INFO L272 TraceCheckUtils]: 24: Hoare triple {1936#true} call __VERIFIER_assert((if ~a~0 == ~y~0 * ~r~0 + ~x~0 * ~p~0 then 1 else 0)); {1936#true} is VALID [2022-04-28 05:23:00,110 INFO L290 TraceCheckUtils]: 25: Hoare triple {1936#true} ~cond := #in~cond; {1936#true} is VALID [2022-04-28 05:23:00,110 INFO L290 TraceCheckUtils]: 26: Hoare triple {1936#true} assume !(0 == ~cond); {1936#true} is VALID [2022-04-28 05:23:00,110 INFO L290 TraceCheckUtils]: 27: Hoare triple {1936#true} assume true; {1936#true} is VALID [2022-04-28 05:23:00,110 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {1936#true} {1936#true} #70#return; {1936#true} is VALID [2022-04-28 05:23:00,110 INFO L272 TraceCheckUtils]: 29: Hoare triple {1936#true} call __VERIFIER_assert((if ~b~0 == ~x~0 * ~q~0 + ~y~0 * ~s~0 then 1 else 0)); {1936#true} is VALID [2022-04-28 05:23:00,110 INFO L290 TraceCheckUtils]: 30: Hoare triple {1936#true} ~cond := #in~cond; {1936#true} is VALID [2022-04-28 05:23:00,110 INFO L290 TraceCheckUtils]: 31: Hoare triple {1936#true} assume !(0 == ~cond); {1936#true} is VALID [2022-04-28 05:23:00,110 INFO L290 TraceCheckUtils]: 32: Hoare triple {1936#true} assume true; {1936#true} is VALID [2022-04-28 05:23:00,110 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {1936#true} {1936#true} #72#return; {1936#true} is VALID [2022-04-28 05:23:00,111 INFO L290 TraceCheckUtils]: 34: Hoare triple {1936#true} assume !(~a~0 != ~b~0); {2043#(= main_~b~0 main_~a~0)} is VALID [2022-04-28 05:23:00,111 INFO L272 TraceCheckUtils]: 35: Hoare triple {2043#(= main_~b~0 main_~a~0)} call __VERIFIER_assert((if 0 == ~a~0 - ~b~0 then 1 else 0)); {2047#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-28 05:23:00,112 INFO L290 TraceCheckUtils]: 36: Hoare triple {2047#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {2051#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 05:23:00,112 INFO L290 TraceCheckUtils]: 37: Hoare triple {2051#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1937#false} is VALID [2022-04-28 05:23:00,112 INFO L290 TraceCheckUtils]: 38: Hoare triple {1937#false} assume !false; {1937#false} is VALID [2022-04-28 05:23:00,112 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-04-28 05:23:00,112 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-28 05:23:00,112 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 05:23:00,113 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1191902080] [2022-04-28 05:23:00,113 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 05:23:00,113 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [567400280] [2022-04-28 05:23:00,113 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [567400280] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 05:23:00,113 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 05:23:00,113 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 05:23:00,113 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 05:23:00,113 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [588532860] [2022-04-28 05:23:00,113 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [588532860] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 05:23:00,113 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 05:23:00,113 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 05:23:00,113 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [37750010] [2022-04-28 05:23:00,113 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 05:23:00,114 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 39 [2022-04-28 05:23:00,114 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 05:23:00,114 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2022-04-28 05:23:00,131 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 30 edges. 30 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:23:00,131 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 05:23:00,131 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 05:23:00,131 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 05:23:00,131 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-28 05:23:00,132 INFO L87 Difference]: Start difference. First operand 71 states and 100 transitions. Second operand has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2022-04-28 05:23:00,273 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:23:00,273 INFO L93 Difference]: Finished difference Result 87 states and 123 transitions. [2022-04-28 05:23:00,274 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-28 05:23:00,274 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 39 [2022-04-28 05:23:00,274 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 05:23:00,274 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2022-04-28 05:23:00,275 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 51 transitions. [2022-04-28 05:23:00,275 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2022-04-28 05:23:00,276 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 51 transitions. [2022-04-28 05:23:00,276 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 51 transitions. [2022-04-28 05:23:00,311 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-28 05:23:00,313 INFO L225 Difference]: With dead ends: 87 [2022-04-28 05:23:00,313 INFO L226 Difference]: Without dead ends: 85 [2022-04-28 05:23:00,314 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 35 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-28 05:23:00,314 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 5 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-28 05:23:00,315 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 144 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-28 05:23:00,315 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2022-04-28 05:23:00,334 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 78. [2022-04-28 05:23:00,334 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 05:23:00,335 INFO L82 GeneralOperation]: Start isEquivalent. First operand 85 states. Second operand has 78 states, 39 states have (on average 1.3076923076923077) internal successors, (51), 46 states have internal predecessors, (51), 31 states have call successors, (31), 8 states have call predecessors, (31), 7 states have return successors, (27), 23 states have call predecessors, (27), 27 states have call successors, (27) [2022-04-28 05:23:00,335 INFO L74 IsIncluded]: Start isIncluded. First operand 85 states. Second operand has 78 states, 39 states have (on average 1.3076923076923077) internal successors, (51), 46 states have internal predecessors, (51), 31 states have call successors, (31), 8 states have call predecessors, (31), 7 states have return successors, (27), 23 states have call predecessors, (27), 27 states have call successors, (27) [2022-04-28 05:23:00,335 INFO L87 Difference]: Start difference. First operand 85 states. Second operand has 78 states, 39 states have (on average 1.3076923076923077) internal successors, (51), 46 states have internal predecessors, (51), 31 states have call successors, (31), 8 states have call predecessors, (31), 7 states have return successors, (27), 23 states have call predecessors, (27), 27 states have call successors, (27) [2022-04-28 05:23:00,338 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:23:00,338 INFO L93 Difference]: Finished difference Result 85 states and 121 transitions. [2022-04-28 05:23:00,338 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 121 transitions. [2022-04-28 05:23:00,338 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 05:23:00,338 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 05:23:00,339 INFO L74 IsIncluded]: Start isIncluded. First operand has 78 states, 39 states have (on average 1.3076923076923077) internal successors, (51), 46 states have internal predecessors, (51), 31 states have call successors, (31), 8 states have call predecessors, (31), 7 states have return successors, (27), 23 states have call predecessors, (27), 27 states have call successors, (27) Second operand 85 states. [2022-04-28 05:23:00,339 INFO L87 Difference]: Start difference. First operand has 78 states, 39 states have (on average 1.3076923076923077) internal successors, (51), 46 states have internal predecessors, (51), 31 states have call successors, (31), 8 states have call predecessors, (31), 7 states have return successors, (27), 23 states have call predecessors, (27), 27 states have call successors, (27) Second operand 85 states. [2022-04-28 05:23:00,342 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 05:23:00,342 INFO L93 Difference]: Finished difference Result 85 states and 121 transitions. [2022-04-28 05:23:00,342 INFO L276 IsEmpty]: Start isEmpty. Operand 85 states and 121 transitions. [2022-04-28 05:23:00,342 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 05:23:00,342 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 05:23:00,342 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 05:23:00,342 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 05:23:00,342 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 39 states have (on average 1.3076923076923077) internal successors, (51), 46 states have internal predecessors, (51), 31 states have call successors, (31), 8 states have call predecessors, (31), 7 states have return successors, (27), 23 states have call predecessors, (27), 27 states have call successors, (27) [2022-04-28 05:23:00,345 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 109 transitions. [2022-04-28 05:23:00,345 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 109 transitions. Word has length 39 [2022-04-28 05:23:00,345 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 05:23:00,345 INFO L495 AbstractCegarLoop]: Abstraction has 78 states and 109 transitions. [2022-04-28 05:23:00,345 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2022-04-28 05:23:00,345 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 78 states and 109 transitions. [2022-04-28 05:23:00,450 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 109 edges. 109 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 05:23:00,451 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 109 transitions. [2022-04-28 05:23:00,451 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-04-28 05:23:00,451 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 05:23:00,451 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 05:23:00,469 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-28 05:23:00,668 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 05:23:00,669 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 05:23:00,669 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 05:23:00,669 INFO L85 PathProgramCache]: Analyzing trace with hash -1085077998, now seen corresponding path program 1 times [2022-04-28 05:23:00,669 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 05:23:00,669 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [293031310] [2022-04-28 05:23:00,669 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 05:23:00,669 INFO L85 PathProgramCache]: Analyzing trace with hash -1085077998, now seen corresponding path program 2 times [2022-04-28 05:23:00,670 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 05:23:00,670 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1399370312] [2022-04-28 05:23:00,670 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 05:23:00,670 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 05:23:00,689 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 05:23:00,690 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1473455678] [2022-04-28 05:23:00,690 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 05:23:00,690 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 05:23:00,690 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 05:23:00,691 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-28 05:23:00,701 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-28 05:23:00,747 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-28 05:23:00,747 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2022-04-28 05:23:00,747 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-04-28 05:23:00,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-04-28 05:23:00,775 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-04-28 05:23:00,775 INFO L130 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found a feasible trace [2022-04-28 05:23:00,775 INFO L271 BasicCegarLoop]: Counterexample is feasible [2022-04-28 05:23:00,777 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-28 05:23:00,797 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-28 05:23:00,995 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 05:23:00,997 INFO L356 BasicCegarLoop]: Path program histogram: [2, 2, 2, 2, 2, 2, 2] [2022-04-28 05:23:01,000 INFO L176 ceAbstractionStarter]: Computing trace abstraction results [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: reach_errorENTRY has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: ULTIMATE.initENTRY has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: ULTIMATE.startENTRY has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: ULTIMATE.startENTRY has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: assume_abort_if_notENTRY has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: mainENTRY has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: __VERIFIER_assertENTRY has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: reach_errorFINAL has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: ULTIMATE.initFINAL has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: L-1 has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: L-1 has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: L8 has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: L8 has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: L24 has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: L24 has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: L11 has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: L11 has no Hoare annotation [2022-04-28 05:23:01,019 WARN L170 areAnnotationChecker]: ULTIMATE.initEXIT has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: ULTIMATE.startFINAL has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L8-2 has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L24-1 has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L24-1 has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L12 has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L12 has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L11-2 has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: assume_abort_if_notEXIT has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: assume_abort_if_notEXIT has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L25 has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: __VERIFIER_assertEXIT has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L42-2 has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L42-2 has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L35-1 has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L35-1 has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L36 has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L36 has no Hoare annotation [2022-04-28 05:23:01,020 WARN L170 areAnnotationChecker]: L37 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L37 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L53 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L53 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L54 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L54 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L55 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L55 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L56 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L34-3 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L34-3 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L34-1 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L34-1 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L42 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L42 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: mainFINAL has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L35 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: L35 has no Hoare annotation [2022-04-28 05:23:01,021 WARN L170 areAnnotationChecker]: mainEXIT has no Hoare annotation [2022-04-28 05:23:01,021 INFO L163 areAnnotationChecker]: CFG has 0 edges. 0 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. 0 times interpolants missing. [2022-04-28 05:23:01,023 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 28.04 05:23:01 BoogieIcfgContainer [2022-04-28 05:23:01,023 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-28 05:23:01,024 INFO L158 Benchmark]: Toolchain (without parser) took 11912.97ms. Allocated memory was 211.8MB in the beginning and 265.3MB in the end (delta: 53.5MB). Free memory was 156.4MB in the beginning and 148.4MB in the end (delta: 8.1MB). Peak memory consumption was 61.3MB. Max. memory is 8.0GB. [2022-04-28 05:23:01,024 INFO L158 Benchmark]: CDTParser took 0.10ms. Allocated memory is still 211.8MB. Free memory was 173.3MB in the beginning and 173.2MB in the end (delta: 77.0kB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-28 05:23:01,024 INFO L158 Benchmark]: CACSL2BoogieTranslator took 200.29ms. Allocated memory was 211.8MB in the beginning and 265.3MB in the end (delta: 53.5MB). Free memory was 156.3MB in the beginning and 237.7MB in the end (delta: -81.4MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. [2022-04-28 05:23:01,024 INFO L158 Benchmark]: Boogie Preprocessor took 31.26ms. Allocated memory is still 265.3MB. Free memory was 237.7MB in the beginning and 236.2MB in the end (delta: 1.6MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-28 05:23:01,025 INFO L158 Benchmark]: RCFGBuilder took 247.85ms. Allocated memory is still 265.3MB. Free memory was 236.2MB in the beginning and 222.5MB in the end (delta: 13.6MB). Peak memory consumption was 13.6MB. Max. memory is 8.0GB. [2022-04-28 05:23:01,025 INFO L158 Benchmark]: TraceAbstraction took 11429.25ms. Allocated memory is still 265.3MB. Free memory was 222.0MB in the beginning and 148.4MB in the end (delta: 73.6MB). Peak memory consumption was 74.2MB. Max. memory is 8.0GB. [2022-04-28 05:23:01,026 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.10ms. Allocated memory is still 211.8MB. Free memory was 173.3MB in the beginning and 173.2MB in the end (delta: 77.0kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 200.29ms. Allocated memory was 211.8MB in the beginning and 265.3MB in the end (delta: 53.5MB). Free memory was 156.3MB in the beginning and 237.7MB in the end (delta: -81.4MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. * Boogie Preprocessor took 31.26ms. Allocated memory is still 265.3MB. Free memory was 237.7MB in the beginning and 236.2MB in the end (delta: 1.6MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 247.85ms. Allocated memory is still 265.3MB. Free memory was 236.2MB in the beginning and 222.5MB in the end (delta: 13.6MB). Peak memory consumption was 13.6MB. Max. memory is 8.0GB. * TraceAbstraction took 11429.25ms. Allocated memory is still 265.3MB. Free memory was 222.0MB in the beginning and 148.4MB in the end (delta: 73.6MB). Peak memory consumption was 74.2MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 13]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L18] int counter = 0; [L20] long long a, b, p, q, r, s; [L21] int x, y; [L22] x = __VERIFIER_nondet_int() [L23] y = __VERIFIER_nondet_int() [L24] CALL assume_abort_if_not(x >= 1) [L8] COND FALSE !(!cond) [L24] RET assume_abort_if_not(x >= 1) [L25] CALL assume_abort_if_not(y >= 1) [L8] COND FALSE !(!cond) [L25] RET assume_abort_if_not(y >= 1) [L27] a = x [L28] b = y [L29] p = 1 [L30] q = 0 [L31] r = 0 [L32] s = 1 [L34] EXPR counter++ [L34] COND TRUE counter++<1 [L35] CALL __VERIFIER_assert(1 == p * s - r * q) [L11] COND FALSE !(!(cond)) [L35] RET __VERIFIER_assert(1 == p * s - r * q) [L36] CALL __VERIFIER_assert(a == y * r + x * p) [L11] COND FALSE !(!(cond)) [L36] RET __VERIFIER_assert(a == y * r + x * p) [L37] CALL __VERIFIER_assert(b == x * q + y * s) [L11] COND FALSE !(!(cond)) [L37] RET __VERIFIER_assert(b == x * q + y * s) [L39] COND FALSE !(!(a != b)) [L42] COND TRUE a > b [L43] a = a - b [L44] p = p - q [L45] r = r - s [L34] EXPR counter++ [L34] COND FALSE !(counter++<1) [L53] CALL __VERIFIER_assert(a - b == 0) [L11] COND TRUE !(cond) [L13] reach_error() - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 38 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 11.4s, OverallIterations: 7, TraceHistogramMax: 4, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 1.5s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 74 SdHoareTripleChecker+Valid, 0.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 54 mSDsluCounter, 654 SdHoareTripleChecker+Invalid, 0.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 408 mSDsCounter, 27 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 258 IncrementalHoareTripleChecker+Invalid, 285 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 27 mSolverCounterUnsat, 246 mSDtfsCounter, 258 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 178 GetRequests, 152 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=78occurred in iteration=6, InterpolantAutomatonStates: 29, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 6 MinimizatonAttempts, 10 StatesRemovedByMinimization, 4 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: No data available, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2022-04-28 05:23:01,048 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...