/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/geo3-ll_valuebound50.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-e106359-m [2022-04-15 09:13:21,437 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-15 09:13:21,478 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-15 09:13:21,514 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-15 09:13:21,514 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-15 09:13:21,516 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-15 09:13:21,521 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-15 09:13:21,527 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-15 09:13:21,529 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-15 09:13:21,534 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-15 09:13:21,535 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-15 09:13:21,535 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-15 09:13:21,536 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-15 09:13:21,536 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-15 09:13:21,537 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-15 09:13:21,538 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-15 09:13:21,538 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-15 09:13:21,539 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-15 09:13:21,540 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-15 09:13:21,541 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-15 09:13:21,542 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-15 09:13:21,545 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-15 09:13:21,546 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-15 09:13:21,547 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-15 09:13:21,548 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-15 09:13:21,556 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-15 09:13:21,556 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-15 09:13:21,557 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-15 09:13:21,557 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-15 09:13:21,557 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-15 09:13:21,559 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-15 09:13:21,559 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-15 09:13:21,560 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-15 09:13:21,561 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-15 09:13:21,561 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-15 09:13:21,562 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-15 09:13:21,562 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-15 09:13:21,563 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-15 09:13:21,563 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-15 09:13:21,563 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-15 09:13:21,564 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-15 09:13:21,566 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-15 09:13:21,566 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-04-15 09:13:21,576 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-15 09:13:21,576 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-15 09:13:21,577 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-15 09:13:21,577 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-15 09:13:21,577 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-15 09:13:21,578 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-15 09:13:21,578 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-15 09:13:21,578 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-15 09:13:21,578 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-15 09:13:21,579 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-15 09:13:21,579 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-15 09:13:21,579 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-15 09:13:21,579 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-15 09:13:21,580 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-15 09:13:21,580 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-15 09:13:21,580 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-15 09:13:21,580 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-15 09:13:21,580 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-15 09:13:21,580 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 09:13:21,580 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-15 09:13:21,580 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-15 09:13:21,581 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-15 09:13:21,581 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-15 09:13:21,581 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-15 09:13:21,581 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-15 09:13:21,581 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-15 09:13:21,824 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-15 09:13:21,846 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-15 09:13:21,847 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-15 09:13:21,848 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-15 09:13:21,849 INFO L275 PluginConnector]: CDTParser initialized [2022-04-15 09:13:21,850 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/geo3-ll_valuebound50.c [2022-04-15 09:13:21,902 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/47e7f771e/45e61da0904b4bf799bceb77dc9f16ad/FLAG2b6bfd111 [2022-04-15 09:13:22,276 INFO L306 CDTParser]: Found 1 translation units. [2022-04-15 09:13:22,276 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/geo3-ll_valuebound50.c [2022-04-15 09:13:22,282 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/47e7f771e/45e61da0904b4bf799bceb77dc9f16ad/FLAG2b6bfd111 [2022-04-15 09:13:22,689 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/47e7f771e/45e61da0904b4bf799bceb77dc9f16ad [2022-04-15 09:13:22,691 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-15 09:13:22,692 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-15 09:13:22,695 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-15 09:13:22,696 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-15 09:13:22,699 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-15 09:13:22,700 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 09:13:22" (1/1) ... [2022-04-15 09:13:22,700 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@56f5d36 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:13:22, skipping insertion in model container [2022-04-15 09:13:22,701 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 09:13:22" (1/1) ... [2022-04-15 09:13:22,706 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-15 09:13:22,718 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-15 09:13:22,845 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/geo3-ll_valuebound50.c[525,538] [2022-04-15 09:13:22,858 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 09:13:22,865 INFO L203 MainTranslator]: Completed pre-run [2022-04-15 09:13:22,880 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/geo3-ll_valuebound50.c[525,538] [2022-04-15 09:13:22,886 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 09:13:22,896 INFO L208 MainTranslator]: Completed translation [2022-04-15 09:13:22,896 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:13:22 WrapperNode [2022-04-15 09:13:22,897 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-15 09:13:22,897 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-15 09:13:22,897 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-15 09:13:22,898 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-15 09:13:22,905 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:13:22" (1/1) ... [2022-04-15 09:13:22,905 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:13:22" (1/1) ... [2022-04-15 09:13:22,909 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:13:22" (1/1) ... [2022-04-15 09:13:22,910 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:13:22" (1/1) ... [2022-04-15 09:13:22,915 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:13:22" (1/1) ... [2022-04-15 09:13:22,919 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:13:22" (1/1) ... [2022-04-15 09:13:22,920 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:13:22" (1/1) ... [2022-04-15 09:13:22,921 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-15 09:13:22,922 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-15 09:13:22,922 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-15 09:13:22,922 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-15 09:13:22,922 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:13:22" (1/1) ... [2022-04-15 09:13:22,928 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 09:13:22,938 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 09:13:22,948 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-15 09:13:22,971 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-15 09:13:22,986 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-15 09:13:22,986 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-15 09:13:22,986 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-15 09:13:22,986 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-15 09:13:22,987 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-15 09:13:22,987 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-15 09:13:22,987 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-15 09:13:22,987 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-15 09:13:22,988 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-15 09:13:22,988 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-15 09:13:22,988 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-15 09:13:22,989 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-15 09:13:22,990 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-15 09:13:22,990 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-15 09:13:22,991 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-15 09:13:22,991 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-15 09:13:22,991 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-15 09:13:22,991 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-15 09:13:22,991 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-15 09:13:22,991 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-15 09:13:23,050 INFO L234 CfgBuilder]: Building ICFG [2022-04-15 09:13:23,052 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-15 09:13:23,250 INFO L275 CfgBuilder]: Performing block encoding [2022-04-15 09:13:23,255 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-15 09:13:23,256 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-15 09:13:23,257 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 09:13:23 BoogieIcfgContainer [2022-04-15 09:13:23,257 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-15 09:13:23,258 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-15 09:13:23,259 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-15 09:13:23,277 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-15 09:13:23,277 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.04 09:13:22" (1/3) ... [2022-04-15 09:13:23,277 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@a9225a2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 09:13:23, skipping insertion in model container [2022-04-15 09:13:23,277 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 09:13:22" (2/3) ... [2022-04-15 09:13:23,278 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@a9225a2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 09:13:23, skipping insertion in model container [2022-04-15 09:13:23,278 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 09:13:23" (3/3) ... [2022-04-15 09:13:23,278 INFO L111 eAbstractionObserver]: Analyzing ICFG geo3-ll_valuebound50.c [2022-04-15 09:13:23,284 INFO L202 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-15 09:13:23,284 INFO L161 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-15 09:13:23,318 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-15 09:13:23,323 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-15 09:13:23,324 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-15 09:13:23,339 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 09:13:23,345 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-04-15 09:13:23,345 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 09:13:23,346 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 09:13:23,346 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 09:13:23,350 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 09:13:23,350 INFO L85 PathProgramCache]: Analyzing trace with hash -779299010, now seen corresponding path program 1 times [2022-04-15 09:13:23,357 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 09:13:23,357 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2021849682] [2022-04-15 09:13:23,367 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 09:13:23,368 INFO L85 PathProgramCache]: Analyzing trace with hash -779299010, now seen corresponding path program 2 times [2022-04-15 09:13:23,370 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 09:13:23,371 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [655992785] [2022-04-15 09:13:23,371 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 09:13:23,371 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 09:13:23,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:13:23,559 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 09:13:23,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:13:23,592 INFO L290 TraceCheckUtils]: 0: Hoare triple {51#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3); {34#true} is VALID [2022-04-15 09:13:23,592 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-15 09:13:23,593 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {34#true} {34#true} #65#return; {34#true} is VALID [2022-04-15 09:13:23,594 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 09:13:23,600 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:13:23,619 INFO L290 TraceCheckUtils]: 0: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-15 09:13:23,620 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-15 09:13:23,620 INFO L290 TraceCheckUtils]: 2: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-15 09:13:23,620 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {35#false} {34#true} #55#return; {35#false} is VALID [2022-04-15 09:13:23,620 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-15 09:13:23,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:13:23,631 INFO L290 TraceCheckUtils]: 0: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-15 09:13:23,632 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-15 09:13:23,632 INFO L290 TraceCheckUtils]: 2: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-15 09:13:23,633 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {35#false} {35#false} #57#return; {35#false} is VALID [2022-04-15 09:13:23,633 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2022-04-15 09:13:23,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:13:23,642 INFO L290 TraceCheckUtils]: 0: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-15 09:13:23,643 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-15 09:13:23,643 INFO L290 TraceCheckUtils]: 2: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-15 09:13:23,644 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {35#false} {35#false} #59#return; {35#false} is VALID [2022-04-15 09:13:23,649 INFO L272 TraceCheckUtils]: 0: Hoare triple {34#true} call ULTIMATE.init(); {51#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 09:13:23,649 INFO L290 TraceCheckUtils]: 1: Hoare triple {51#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3); {34#true} is VALID [2022-04-15 09:13:23,650 INFO L290 TraceCheckUtils]: 2: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-15 09:13:23,650 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {34#true} {34#true} #65#return; {34#true} is VALID [2022-04-15 09:13:23,651 INFO L272 TraceCheckUtils]: 4: Hoare triple {34#true} call #t~ret7 := main(); {34#true} is VALID [2022-04-15 09:13:23,652 INFO L290 TraceCheckUtils]: 5: Hoare triple {34#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {34#true} is VALID [2022-04-15 09:13:23,652 INFO L272 TraceCheckUtils]: 6: Hoare triple {34#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 50 then 1 else 0)); {34#true} is VALID [2022-04-15 09:13:23,652 INFO L290 TraceCheckUtils]: 7: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-15 09:13:23,653 INFO L290 TraceCheckUtils]: 8: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-15 09:13:23,653 INFO L290 TraceCheckUtils]: 9: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-15 09:13:23,653 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {35#false} {34#true} #55#return; {35#false} is VALID [2022-04-15 09:13:23,654 INFO L290 TraceCheckUtils]: 11: Hoare triple {35#false} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {35#false} is VALID [2022-04-15 09:13:23,654 INFO L272 TraceCheckUtils]: 12: Hoare triple {35#false} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 50 then 1 else 0)); {34#true} is VALID [2022-04-15 09:13:23,654 INFO L290 TraceCheckUtils]: 13: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-15 09:13:23,655 INFO L290 TraceCheckUtils]: 14: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-15 09:13:23,655 INFO L290 TraceCheckUtils]: 15: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-15 09:13:23,655 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {35#false} {35#false} #57#return; {35#false} is VALID [2022-04-15 09:13:23,656 INFO L290 TraceCheckUtils]: 17: Hoare triple {35#false} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {35#false} is VALID [2022-04-15 09:13:23,656 INFO L272 TraceCheckUtils]: 18: Hoare triple {35#false} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 50 then 1 else 0)); {34#true} is VALID [2022-04-15 09:13:23,656 INFO L290 TraceCheckUtils]: 19: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-15 09:13:23,657 INFO L290 TraceCheckUtils]: 20: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-15 09:13:23,658 INFO L290 TraceCheckUtils]: 21: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-15 09:13:23,658 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {35#false} {35#false} #59#return; {35#false} is VALID [2022-04-15 09:13:23,658 INFO L290 TraceCheckUtils]: 23: Hoare triple {35#false} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {35#false} is VALID [2022-04-15 09:13:23,658 INFO L290 TraceCheckUtils]: 24: Hoare triple {35#false} assume !true; {35#false} is VALID [2022-04-15 09:13:23,659 INFO L272 TraceCheckUtils]: 25: Hoare triple {35#false} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {35#false} is VALID [2022-04-15 09:13:23,659 INFO L290 TraceCheckUtils]: 26: Hoare triple {35#false} ~cond := #in~cond; {35#false} is VALID [2022-04-15 09:13:23,659 INFO L290 TraceCheckUtils]: 27: Hoare triple {35#false} assume 0 == ~cond; {35#false} is VALID [2022-04-15 09:13:23,659 INFO L290 TraceCheckUtils]: 28: Hoare triple {35#false} assume !false; {35#false} is VALID [2022-04-15 09:13:23,660 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-15 09:13:23,661 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 09:13:23,661 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [655992785] [2022-04-15 09:13:23,662 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [655992785] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:13:23,662 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:13:23,662 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 09:13:23,664 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 09:13:23,665 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2021849682] [2022-04-15 09:13:23,666 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2021849682] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:13:23,666 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:13:23,666 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 09:13:23,666 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2007698742] [2022-04-15 09:13:23,667 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 09:13:23,671 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2022-04-15 09:13:23,673 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 09:13:23,676 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 09:13:23,712 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 23 edges. 23 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:13:23,712 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-15 09:13:23,712 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 09:13:23,735 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-15 09:13:23,735 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 09:13:23,738 INFO L87 Difference]: Start difference. First operand has 31 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 09:13:23,897 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:13:23,898 INFO L93 Difference]: Finished difference Result 55 states and 73 transitions. [2022-04-15 09:13:23,898 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-15 09:13:23,898 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2022-04-15 09:13:23,899 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 09:13:23,901 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 09:13:23,913 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 73 transitions. [2022-04-15 09:13:23,916 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 09:13:23,928 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 73 transitions. [2022-04-15 09:13:23,929 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 73 transitions. [2022-04-15 09:13:24,047 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 73 edges. 73 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:13:24,054 INFO L225 Difference]: With dead ends: 55 [2022-04-15 09:13:24,055 INFO L226 Difference]: Without dead ends: 26 [2022-04-15 09:13:24,057 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 09:13:24,060 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 17 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 09:13:24,060 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 32 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 09:13:24,074 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2022-04-15 09:13:24,088 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2022-04-15 09:13:24,088 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 09:13:24,089 INFO L82 GeneralOperation]: Start isEquivalent. First operand 26 states. Second operand has 26 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-15 09:13:24,090 INFO L74 IsIncluded]: Start isIncluded. First operand 26 states. Second operand has 26 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-15 09:13:24,091 INFO L87 Difference]: Start difference. First operand 26 states. Second operand has 26 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-15 09:13:24,095 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:13:24,095 INFO L93 Difference]: Finished difference Result 26 states and 29 transitions. [2022-04-15 09:13:24,095 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2022-04-15 09:13:24,096 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:13:24,096 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:13:24,097 INFO L74 IsIncluded]: Start isIncluded. First operand has 26 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand 26 states. [2022-04-15 09:13:24,097 INFO L87 Difference]: Start difference. First operand has 26 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand 26 states. [2022-04-15 09:13:24,101 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:13:24,101 INFO L93 Difference]: Finished difference Result 26 states and 29 transitions. [2022-04-15 09:13:24,101 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2022-04-15 09:13:24,102 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:13:24,102 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:13:24,102 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 09:13:24,102 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 09:13:24,103 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-15 09:13:24,106 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2022-04-15 09:13:24,107 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 29 [2022-04-15 09:13:24,107 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 09:13:24,108 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2022-04-15 09:13:24,108 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 09:13:24,109 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 26 states and 29 transitions. [2022-04-15 09:13:24,145 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 29 edges. 29 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:13:24,145 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2022-04-15 09:13:24,146 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-04-15 09:13:24,146 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 09:13:24,146 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 09:13:24,147 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-15 09:13:24,147 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 09:13:24,147 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 09:13:24,148 INFO L85 PathProgramCache]: Analyzing trace with hash -963850242, now seen corresponding path program 1 times [2022-04-15 09:13:24,148 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 09:13:24,148 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1731564627] [2022-04-15 09:13:24,149 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 09:13:24,149 INFO L85 PathProgramCache]: Analyzing trace with hash -963850242, now seen corresponding path program 2 times [2022-04-15 09:13:24,149 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 09:13:24,149 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [32318833] [2022-04-15 09:13:24,149 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 09:13:24,150 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 09:13:24,173 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 09:13:24,174 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [382594033] [2022-04-15 09:13:24,174 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 09:13:24,174 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:13:24,174 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 09:13:24,181 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 09:13:24,191 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-15 09:13:24,242 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-15 09:13:24,243 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 09:13:24,245 INFO L263 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-15 09:13:24,259 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:13:24,263 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 09:13:24,476 INFO L272 TraceCheckUtils]: 0: Hoare triple {268#true} call ULTIMATE.init(); {268#true} is VALID [2022-04-15 09:13:24,477 INFO L290 TraceCheckUtils]: 1: Hoare triple {268#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); {268#true} is VALID [2022-04-15 09:13:24,477 INFO L290 TraceCheckUtils]: 2: Hoare triple {268#true} assume true; {268#true} is VALID [2022-04-15 09:13:24,477 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {268#true} {268#true} #65#return; {268#true} is VALID [2022-04-15 09:13:24,480 INFO L272 TraceCheckUtils]: 4: Hoare triple {268#true} call #t~ret7 := main(); {268#true} is VALID [2022-04-15 09:13:24,480 INFO L290 TraceCheckUtils]: 5: Hoare triple {268#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {268#true} is VALID [2022-04-15 09:13:24,480 INFO L272 TraceCheckUtils]: 6: Hoare triple {268#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 50 then 1 else 0)); {268#true} is VALID [2022-04-15 09:13:24,481 INFO L290 TraceCheckUtils]: 7: Hoare triple {268#true} ~cond := #in~cond; {268#true} is VALID [2022-04-15 09:13:24,481 INFO L290 TraceCheckUtils]: 8: Hoare triple {268#true} assume !(0 == ~cond); {268#true} is VALID [2022-04-15 09:13:24,481 INFO L290 TraceCheckUtils]: 9: Hoare triple {268#true} assume true; {268#true} is VALID [2022-04-15 09:13:24,481 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {268#true} {268#true} #55#return; {268#true} is VALID [2022-04-15 09:13:24,483 INFO L290 TraceCheckUtils]: 11: Hoare triple {268#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {268#true} is VALID [2022-04-15 09:13:24,484 INFO L272 TraceCheckUtils]: 12: Hoare triple {268#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 50 then 1 else 0)); {268#true} is VALID [2022-04-15 09:13:24,484 INFO L290 TraceCheckUtils]: 13: Hoare triple {268#true} ~cond := #in~cond; {268#true} is VALID [2022-04-15 09:13:24,485 INFO L290 TraceCheckUtils]: 14: Hoare triple {268#true} assume !(0 == ~cond); {268#true} is VALID [2022-04-15 09:13:24,485 INFO L290 TraceCheckUtils]: 15: Hoare triple {268#true} assume true; {268#true} is VALID [2022-04-15 09:13:24,485 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {268#true} {268#true} #57#return; {268#true} is VALID [2022-04-15 09:13:24,485 INFO L290 TraceCheckUtils]: 17: Hoare triple {268#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {268#true} is VALID [2022-04-15 09:13:24,486 INFO L272 TraceCheckUtils]: 18: Hoare triple {268#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 50 then 1 else 0)); {268#true} is VALID [2022-04-15 09:13:24,486 INFO L290 TraceCheckUtils]: 19: Hoare triple {268#true} ~cond := #in~cond; {268#true} is VALID [2022-04-15 09:13:24,486 INFO L290 TraceCheckUtils]: 20: Hoare triple {268#true} assume !(0 == ~cond); {268#true} is VALID [2022-04-15 09:13:24,486 INFO L290 TraceCheckUtils]: 21: Hoare triple {268#true} assume true; {268#true} is VALID [2022-04-15 09:13:24,486 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {268#true} {268#true} #59#return; {268#true} is VALID [2022-04-15 09:13:24,487 INFO L290 TraceCheckUtils]: 23: Hoare triple {268#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {342#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:24,488 INFO L290 TraceCheckUtils]: 24: Hoare triple {342#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {342#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:24,489 INFO L272 TraceCheckUtils]: 25: Hoare triple {342#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {349#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:13:24,490 INFO L290 TraceCheckUtils]: 26: Hoare triple {349#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {353#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:13:24,491 INFO L290 TraceCheckUtils]: 27: Hoare triple {353#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {269#false} is VALID [2022-04-15 09:13:24,491 INFO L290 TraceCheckUtils]: 28: Hoare triple {269#false} assume !false; {269#false} is VALID [2022-04-15 09:13:24,491 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-15 09:13:24,491 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 09:13:24,492 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 09:13:24,492 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [32318833] [2022-04-15 09:13:24,492 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 09:13:24,492 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [382594033] [2022-04-15 09:13:24,493 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [382594033] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:13:24,494 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:13:24,494 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 09:13:24,495 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 09:13:24,495 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1731564627] [2022-04-15 09:13:24,495 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1731564627] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:13:24,495 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:13:24,495 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 09:13:24,496 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [635821586] [2022-04-15 09:13:24,496 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 09:13:24,496 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2022-04-15 09:13:24,497 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 09:13:24,498 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-15 09:13:24,520 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 23 edges. 23 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:13:24,521 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 09:13:24,521 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 09:13:24,522 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 09:13:24,522 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 09:13:24,523 INFO L87 Difference]: Start difference. First operand 26 states and 29 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-15 09:13:24,667 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:13:24,667 INFO L93 Difference]: Finished difference Result 36 states and 40 transitions. [2022-04-15 09:13:24,667 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 09:13:24,668 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2022-04-15 09:13:24,668 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 09:13:24,668 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-15 09:13:24,670 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 40 transitions. [2022-04-15 09:13:24,671 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-15 09:13:24,677 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 40 transitions. [2022-04-15 09:13:24,677 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 40 transitions. [2022-04-15 09:13:24,716 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 40 edges. 40 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:13:24,723 INFO L225 Difference]: With dead ends: 36 [2022-04-15 09:13:24,724 INFO L226 Difference]: Without dead ends: 33 [2022-04-15 09:13:24,724 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-15 09:13:24,726 INFO L913 BasicCegarLoop]: 26 mSDtfsCounter, 6 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 09:13:24,730 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 93 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 09:13:24,731 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-04-15 09:13:24,743 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-04-15 09:13:24,743 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 09:13:24,743 INFO L82 GeneralOperation]: Start isEquivalent. First operand 33 states. Second operand has 33 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-15 09:13:24,744 INFO L74 IsIncluded]: Start isIncluded. First operand 33 states. Second operand has 33 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-15 09:13:24,744 INFO L87 Difference]: Start difference. First operand 33 states. Second operand has 33 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-15 09:13:24,747 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:13:24,747 INFO L93 Difference]: Finished difference Result 33 states and 36 transitions. [2022-04-15 09:13:24,747 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 36 transitions. [2022-04-15 09:13:24,749 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:13:24,749 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:13:24,751 INFO L74 IsIncluded]: Start isIncluded. First operand has 33 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand 33 states. [2022-04-15 09:13:24,751 INFO L87 Difference]: Start difference. First operand has 33 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand 33 states. [2022-04-15 09:13:24,753 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:13:24,754 INFO L93 Difference]: Finished difference Result 33 states and 36 transitions. [2022-04-15 09:13:24,754 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 36 transitions. [2022-04-15 09:13:24,754 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:13:24,754 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:13:24,754 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 09:13:24,755 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 09:13:24,755 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-15 09:13:24,759 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 36 transitions. [2022-04-15 09:13:24,760 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 36 transitions. Word has length 29 [2022-04-15 09:13:24,760 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 09:13:24,760 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 36 transitions. [2022-04-15 09:13:24,760 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-15 09:13:24,760 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 33 states and 36 transitions. [2022-04-15 09:13:24,806 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 36 edges. 36 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:13:24,807 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 36 transitions. [2022-04-15 09:13:24,813 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-15 09:13:24,813 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 09:13:24,813 INFO L499 BasicCegarLoop]: trace histogram [3, 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] [2022-04-15 09:13:24,838 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-15 09:13:25,027 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:13:25,028 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 09:13:25,028 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 09:13:25,028 INFO L85 PathProgramCache]: Analyzing trace with hash -425626518, now seen corresponding path program 1 times [2022-04-15 09:13:25,028 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 09:13:25,028 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1251183009] [2022-04-15 09:13:25,029 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 09:13:25,029 INFO L85 PathProgramCache]: Analyzing trace with hash -425626518, now seen corresponding path program 2 times [2022-04-15 09:13:25,029 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 09:13:25,029 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [16317554] [2022-04-15 09:13:25,030 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 09:13:25,030 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 09:13:25,051 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 09:13:25,052 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1312777336] [2022-04-15 09:13:25,052 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 09:13:25,052 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:13:25,052 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 09:13:25,054 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 09:13:25,055 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-15 09:13:25,114 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 09:13:25,115 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 09:13:25,116 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 27 conjunts are in the unsatisfiable core [2022-04-15 09:13:25,131 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:13:25,133 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 09:13:25,461 INFO L272 TraceCheckUtils]: 0: Hoare triple {565#true} call ULTIMATE.init(); {565#true} is VALID [2022-04-15 09:13:25,461 INFO L290 TraceCheckUtils]: 1: Hoare triple {565#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); {565#true} is VALID [2022-04-15 09:13:25,461 INFO L290 TraceCheckUtils]: 2: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-15 09:13:25,461 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {565#true} {565#true} #65#return; {565#true} is VALID [2022-04-15 09:13:25,461 INFO L272 TraceCheckUtils]: 4: Hoare triple {565#true} call #t~ret7 := main(); {565#true} is VALID [2022-04-15 09:13:25,461 INFO L290 TraceCheckUtils]: 5: Hoare triple {565#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {565#true} is VALID [2022-04-15 09:13:25,462 INFO L272 TraceCheckUtils]: 6: Hoare triple {565#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 50 then 1 else 0)); {565#true} is VALID [2022-04-15 09:13:25,462 INFO L290 TraceCheckUtils]: 7: Hoare triple {565#true} ~cond := #in~cond; {565#true} is VALID [2022-04-15 09:13:25,462 INFO L290 TraceCheckUtils]: 8: Hoare triple {565#true} assume !(0 == ~cond); {565#true} is VALID [2022-04-15 09:13:25,462 INFO L290 TraceCheckUtils]: 9: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-15 09:13:25,462 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {565#true} {565#true} #55#return; {565#true} is VALID [2022-04-15 09:13:25,463 INFO L290 TraceCheckUtils]: 11: Hoare triple {565#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {565#true} is VALID [2022-04-15 09:13:25,463 INFO L272 TraceCheckUtils]: 12: Hoare triple {565#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 50 then 1 else 0)); {565#true} is VALID [2022-04-15 09:13:25,463 INFO L290 TraceCheckUtils]: 13: Hoare triple {565#true} ~cond := #in~cond; {565#true} is VALID [2022-04-15 09:13:25,463 INFO L290 TraceCheckUtils]: 14: Hoare triple {565#true} assume !(0 == ~cond); {565#true} is VALID [2022-04-15 09:13:25,463 INFO L290 TraceCheckUtils]: 15: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-15 09:13:25,463 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {565#true} {565#true} #57#return; {565#true} is VALID [2022-04-15 09:13:25,463 INFO L290 TraceCheckUtils]: 17: Hoare triple {565#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {565#true} is VALID [2022-04-15 09:13:25,464 INFO L272 TraceCheckUtils]: 18: Hoare triple {565#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 50 then 1 else 0)); {565#true} is VALID [2022-04-15 09:13:25,464 INFO L290 TraceCheckUtils]: 19: Hoare triple {565#true} ~cond := #in~cond; {627#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-15 09:13:25,465 INFO L290 TraceCheckUtils]: 20: Hoare triple {627#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {631#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-15 09:13:25,465 INFO L290 TraceCheckUtils]: 21: Hoare triple {631#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {631#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-15 09:13:25,465 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {631#(not (= |assume_abort_if_not_#in~cond| 0))} {565#true} #59#return; {565#true} is VALID [2022-04-15 09:13:25,466 INFO L290 TraceCheckUtils]: 23: Hoare triple {565#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:25,466 INFO L290 TraceCheckUtils]: 24: Hoare triple {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:25,466 INFO L272 TraceCheckUtils]: 25: Hoare triple {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {565#true} is VALID [2022-04-15 09:13:25,467 INFO L290 TraceCheckUtils]: 26: Hoare triple {565#true} ~cond := #in~cond; {651#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:13:25,467 INFO L290 TraceCheckUtils]: 27: Hoare triple {651#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {655#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:13:25,470 INFO L290 TraceCheckUtils]: 28: Hoare triple {655#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {655#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:13:25,470 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {655#(not (= |__VERIFIER_assert_#in~cond| 0))} {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} #61#return; {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:25,471 INFO L290 TraceCheckUtils]: 30: Hoare triple {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {665#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:25,472 INFO L290 TraceCheckUtils]: 31: Hoare triple {665#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {665#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:25,475 INFO L272 TraceCheckUtils]: 32: Hoare triple {665#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {672#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:13:25,476 INFO L290 TraceCheckUtils]: 33: Hoare triple {672#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {676#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:13:25,476 INFO L290 TraceCheckUtils]: 34: Hoare triple {676#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {566#false} is VALID [2022-04-15 09:13:25,476 INFO L290 TraceCheckUtils]: 35: Hoare triple {566#false} assume !false; {566#false} is VALID [2022-04-15 09:13:25,476 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 7 proven. 3 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-04-15 09:13:25,477 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-15 09:13:40,112 INFO L290 TraceCheckUtils]: 35: Hoare triple {566#false} assume !false; {566#false} is VALID [2022-04-15 09:13:40,113 INFO L290 TraceCheckUtils]: 34: Hoare triple {676#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {566#false} is VALID [2022-04-15 09:13:40,113 INFO L290 TraceCheckUtils]: 33: Hoare triple {672#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {676#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:13:40,114 INFO L272 TraceCheckUtils]: 32: Hoare triple {692#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {672#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:13:40,115 INFO L290 TraceCheckUtils]: 31: Hoare triple {692#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} assume !false; {692#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} is VALID [2022-04-15 09:13:40,179 INFO L290 TraceCheckUtils]: 30: Hoare triple {699#(= (+ (* main_~z~0 main_~x~0) main_~a~0 (* main_~az~0 (* main_~z~0 main_~y~0))) (+ main_~a~0 (* main_~z~0 (+ (* main_~z~0 main_~x~0) main_~a~0))))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {692#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} is VALID [2022-04-15 09:13:40,182 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {655#(not (= |__VERIFIER_assert_#in~cond| 0))} {565#true} #61#return; {699#(= (+ (* main_~z~0 main_~x~0) main_~a~0 (* main_~az~0 (* main_~z~0 main_~y~0))) (+ main_~a~0 (* main_~z~0 (+ (* main_~z~0 main_~x~0) main_~a~0))))} is VALID [2022-04-15 09:13:40,183 INFO L290 TraceCheckUtils]: 28: Hoare triple {655#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {655#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:13:40,183 INFO L290 TraceCheckUtils]: 27: Hoare triple {712#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {655#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:13:40,184 INFO L290 TraceCheckUtils]: 26: Hoare triple {565#true} ~cond := #in~cond; {712#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 09:13:40,184 INFO L272 TraceCheckUtils]: 25: Hoare triple {565#true} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {565#true} is VALID [2022-04-15 09:13:40,184 INFO L290 TraceCheckUtils]: 24: Hoare triple {565#true} assume !false; {565#true} is VALID [2022-04-15 09:13:40,184 INFO L290 TraceCheckUtils]: 23: Hoare triple {565#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {565#true} is VALID [2022-04-15 09:13:40,184 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {565#true} {565#true} #59#return; {565#true} is VALID [2022-04-15 09:13:40,184 INFO L290 TraceCheckUtils]: 21: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-15 09:13:40,185 INFO L290 TraceCheckUtils]: 20: Hoare triple {565#true} assume !(0 == ~cond); {565#true} is VALID [2022-04-15 09:13:40,185 INFO L290 TraceCheckUtils]: 19: Hoare triple {565#true} ~cond := #in~cond; {565#true} is VALID [2022-04-15 09:13:40,185 INFO L272 TraceCheckUtils]: 18: Hoare triple {565#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 50 then 1 else 0)); {565#true} is VALID [2022-04-15 09:13:40,185 INFO L290 TraceCheckUtils]: 17: Hoare triple {565#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {565#true} is VALID [2022-04-15 09:13:40,185 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {565#true} {565#true} #57#return; {565#true} is VALID [2022-04-15 09:13:40,185 INFO L290 TraceCheckUtils]: 15: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-15 09:13:40,185 INFO L290 TraceCheckUtils]: 14: Hoare triple {565#true} assume !(0 == ~cond); {565#true} is VALID [2022-04-15 09:13:40,186 INFO L290 TraceCheckUtils]: 13: Hoare triple {565#true} ~cond := #in~cond; {565#true} is VALID [2022-04-15 09:13:40,186 INFO L272 TraceCheckUtils]: 12: Hoare triple {565#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 50 then 1 else 0)); {565#true} is VALID [2022-04-15 09:13:40,186 INFO L290 TraceCheckUtils]: 11: Hoare triple {565#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {565#true} is VALID [2022-04-15 09:13:40,186 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {565#true} {565#true} #55#return; {565#true} is VALID [2022-04-15 09:13:40,186 INFO L290 TraceCheckUtils]: 9: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-15 09:13:40,186 INFO L290 TraceCheckUtils]: 8: Hoare triple {565#true} assume !(0 == ~cond); {565#true} is VALID [2022-04-15 09:13:40,187 INFO L290 TraceCheckUtils]: 7: Hoare triple {565#true} ~cond := #in~cond; {565#true} is VALID [2022-04-15 09:13:40,187 INFO L272 TraceCheckUtils]: 6: Hoare triple {565#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 50 then 1 else 0)); {565#true} is VALID [2022-04-15 09:13:40,187 INFO L290 TraceCheckUtils]: 5: Hoare triple {565#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {565#true} is VALID [2022-04-15 09:13:40,187 INFO L272 TraceCheckUtils]: 4: Hoare triple {565#true} call #t~ret7 := main(); {565#true} is VALID [2022-04-15 09:13:40,187 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {565#true} {565#true} #65#return; {565#true} is VALID [2022-04-15 09:13:40,187 INFO L290 TraceCheckUtils]: 2: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-15 09:13:40,187 INFO L290 TraceCheckUtils]: 1: Hoare triple {565#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); {565#true} is VALID [2022-04-15 09:13:40,188 INFO L272 TraceCheckUtils]: 0: Hoare triple {565#true} call ULTIMATE.init(); {565#true} is VALID [2022-04-15 09:13:40,188 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-15 09:13:40,188 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 09:13:40,188 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [16317554] [2022-04-15 09:13:40,188 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 09:13:40,188 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1312777336] [2022-04-15 09:13:40,189 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1312777336] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-15 09:13:40,189 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-15 09:13:40,189 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 13 [2022-04-15 09:13:40,189 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 09:13:40,189 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1251183009] [2022-04-15 09:13:40,189 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1251183009] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:13:40,189 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:13:40,190 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-04-15 09:13:40,190 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [108050662] [2022-04-15 09:13:40,190 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 09:13:40,190 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2022-04-15 09:13:40,191 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 09:13:40,191 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 09:13:40,266 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 33 edges. 33 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:13:40,266 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-15 09:13:40,266 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 09:13:40,266 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-15 09:13:40,267 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2022-04-15 09:13:40,267 INFO L87 Difference]: Start difference. First operand 33 states and 36 transitions. Second operand has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 09:13:41,348 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:13:41,349 INFO L93 Difference]: Finished difference Result 43 states and 47 transitions. [2022-04-15 09:13:41,349 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-15 09:13:41,349 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2022-04-15 09:13:41,349 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 09:13:41,349 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 09:13:41,351 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 44 transitions. [2022-04-15 09:13:41,351 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 09:13:41,353 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 44 transitions. [2022-04-15 09:13:41,353 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 10 states and 44 transitions. [2022-04-15 09:13:41,442 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:13:41,444 INFO L225 Difference]: With dead ends: 43 [2022-04-15 09:13:41,444 INFO L226 Difference]: Without dead ends: 40 [2022-04-15 09:13:41,445 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 59 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=49, Invalid=191, Unknown=0, NotChecked=0, Total=240 [2022-04-15 09:13:41,445 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 14 mSDsluCounter, 127 mSDsCounter, 0 mSdLazyCounter, 137 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 140 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 137 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-04-15 09:13:41,446 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 149 Invalid, 140 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 137 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-04-15 09:13:41,446 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2022-04-15 09:13:41,464 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 40. [2022-04-15 09:13:41,464 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 09:13:41,465 INFO L82 GeneralOperation]: Start isEquivalent. First operand 40 states. Second operand has 40 states, 25 states have (on average 1.08) internal successors, (27), 26 states have internal predecessors, (27), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 09:13:41,466 INFO L74 IsIncluded]: Start isIncluded. First operand 40 states. Second operand has 40 states, 25 states have (on average 1.08) internal successors, (27), 26 states have internal predecessors, (27), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 09:13:41,467 INFO L87 Difference]: Start difference. First operand 40 states. Second operand has 40 states, 25 states have (on average 1.08) internal successors, (27), 26 states have internal predecessors, (27), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 09:13:41,469 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:13:41,469 INFO L93 Difference]: Finished difference Result 40 states and 43 transitions. [2022-04-15 09:13:41,469 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 43 transitions. [2022-04-15 09:13:41,470 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:13:41,470 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:13:41,470 INFO L74 IsIncluded]: Start isIncluded. First operand has 40 states, 25 states have (on average 1.08) internal successors, (27), 26 states have internal predecessors, (27), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 40 states. [2022-04-15 09:13:41,470 INFO L87 Difference]: Start difference. First operand has 40 states, 25 states have (on average 1.08) internal successors, (27), 26 states have internal predecessors, (27), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 40 states. [2022-04-15 09:13:41,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:13:41,472 INFO L93 Difference]: Finished difference Result 40 states and 43 transitions. [2022-04-15 09:13:41,472 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 43 transitions. [2022-04-15 09:13:41,472 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:13:41,472 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:13:41,472 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 09:13:41,472 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 09:13:41,473 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 25 states have (on average 1.08) internal successors, (27), 26 states have internal predecessors, (27), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-15 09:13:41,474 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 43 transitions. [2022-04-15 09:13:41,474 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 43 transitions. Word has length 36 [2022-04-15 09:13:41,474 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 09:13:41,474 INFO L478 AbstractCegarLoop]: Abstraction has 40 states and 43 transitions. [2022-04-15 09:13:41,474 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 09:13:41,474 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 40 states and 43 transitions. [2022-04-15 09:13:41,556 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 43 edges. 43 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:13:41,556 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 43 transitions. [2022-04-15 09:13:41,557 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-04-15 09:13:41,557 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 09:13:41,557 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 09:13:41,575 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-15 09:13:41,759 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-04-15 09:13:41,759 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 09:13:41,760 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 09:13:41,760 INFO L85 PathProgramCache]: Analyzing trace with hash 1540046462, now seen corresponding path program 3 times [2022-04-15 09:13:41,760 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 09:13:41,760 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1125160443] [2022-04-15 09:13:41,760 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 09:13:41,761 INFO L85 PathProgramCache]: Analyzing trace with hash 1540046462, now seen corresponding path program 4 times [2022-04-15 09:13:41,761 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 09:13:41,761 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1668488059] [2022-04-15 09:13:41,761 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 09:13:41,761 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 09:13:41,788 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 09:13:41,788 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [446000941] [2022-04-15 09:13:41,788 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-15 09:13:41,788 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:13:41,789 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 09:13:41,790 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 09:13:41,803 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-15 09:13:41,851 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-15 09:13:41,851 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 09:13:41,852 INFO L263 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 27 conjunts are in the unsatisfiable core [2022-04-15 09:13:43,324 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:13:43,326 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 09:13:43,687 INFO L272 TraceCheckUtils]: 0: Hoare triple {1045#true} call ULTIMATE.init(); {1045#true} is VALID [2022-04-15 09:13:43,687 INFO L290 TraceCheckUtils]: 1: Hoare triple {1045#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); {1045#true} is VALID [2022-04-15 09:13:43,687 INFO L290 TraceCheckUtils]: 2: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-15 09:13:43,687 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1045#true} {1045#true} #65#return; {1045#true} is VALID [2022-04-15 09:13:43,688 INFO L272 TraceCheckUtils]: 4: Hoare triple {1045#true} call #t~ret7 := main(); {1045#true} is VALID [2022-04-15 09:13:43,688 INFO L290 TraceCheckUtils]: 5: Hoare triple {1045#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {1045#true} is VALID [2022-04-15 09:13:43,688 INFO L272 TraceCheckUtils]: 6: Hoare triple {1045#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 50 then 1 else 0)); {1045#true} is VALID [2022-04-15 09:13:43,688 INFO L290 TraceCheckUtils]: 7: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-15 09:13:43,690 INFO L290 TraceCheckUtils]: 8: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-15 09:13:43,690 INFO L290 TraceCheckUtils]: 9: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-15 09:13:43,690 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1045#true} {1045#true} #55#return; {1045#true} is VALID [2022-04-15 09:13:43,690 INFO L290 TraceCheckUtils]: 11: Hoare triple {1045#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {1045#true} is VALID [2022-04-15 09:13:43,691 INFO L272 TraceCheckUtils]: 12: Hoare triple {1045#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 50 then 1 else 0)); {1045#true} is VALID [2022-04-15 09:13:43,691 INFO L290 TraceCheckUtils]: 13: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-15 09:13:43,691 INFO L290 TraceCheckUtils]: 14: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-15 09:13:43,691 INFO L290 TraceCheckUtils]: 15: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-15 09:13:43,691 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1045#true} {1045#true} #57#return; {1045#true} is VALID [2022-04-15 09:13:43,691 INFO L290 TraceCheckUtils]: 17: Hoare triple {1045#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {1045#true} is VALID [2022-04-15 09:13:43,691 INFO L272 TraceCheckUtils]: 18: Hoare triple {1045#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 50 then 1 else 0)); {1045#true} is VALID [2022-04-15 09:13:43,691 INFO L290 TraceCheckUtils]: 19: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-15 09:13:43,692 INFO L290 TraceCheckUtils]: 20: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-15 09:13:43,692 INFO L290 TraceCheckUtils]: 21: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-15 09:13:43,692 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1045#true} {1045#true} #59#return; {1045#true} is VALID [2022-04-15 09:13:43,693 INFO L290 TraceCheckUtils]: 23: Hoare triple {1045#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:43,694 INFO L290 TraceCheckUtils]: 24: Hoare triple {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:43,706 INFO L272 TraceCheckUtils]: 25: Hoare triple {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1045#true} is VALID [2022-04-15 09:13:43,707 INFO L290 TraceCheckUtils]: 26: Hoare triple {1045#true} ~cond := #in~cond; {1129#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:13:43,707 INFO L290 TraceCheckUtils]: 27: Hoare triple {1129#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:13:43,708 INFO L290 TraceCheckUtils]: 28: Hoare triple {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:13:43,709 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} #61#return; {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:43,710 INFO L290 TraceCheckUtils]: 30: Hoare triple {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:43,710 INFO L290 TraceCheckUtils]: 31: Hoare triple {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:43,710 INFO L272 TraceCheckUtils]: 32: Hoare triple {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1045#true} is VALID [2022-04-15 09:13:43,711 INFO L290 TraceCheckUtils]: 33: Hoare triple {1045#true} ~cond := #in~cond; {1129#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:13:43,711 INFO L290 TraceCheckUtils]: 34: Hoare triple {1129#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:13:43,712 INFO L290 TraceCheckUtils]: 35: Hoare triple {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:13:43,713 INFO L284 TraceCheckUtils]: 36: Hoare quadruple {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} #61#return; {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:43,715 INFO L290 TraceCheckUtils]: 37: Hoare triple {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1165#(and (= main_~x~0 (+ (* main_~z~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) main_~a~0)) (= (* main_~z~0 main_~z~0) main_~y~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:43,716 INFO L290 TraceCheckUtils]: 38: Hoare triple {1165#(and (= main_~x~0 (+ (* main_~z~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) main_~a~0)) (= (* main_~z~0 main_~z~0) main_~y~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {1165#(and (= main_~x~0 (+ (* main_~z~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) main_~a~0)) (= (* main_~z~0 main_~z~0) main_~y~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:13:43,731 INFO L272 TraceCheckUtils]: 39: Hoare triple {1165#(and (= main_~x~0 (+ (* main_~z~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) main_~a~0)) (= (* main_~z~0 main_~z~0) main_~y~0) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1172#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:13:43,735 INFO L290 TraceCheckUtils]: 40: Hoare triple {1172#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1176#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:13:43,736 INFO L290 TraceCheckUtils]: 41: Hoare triple {1176#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1046#false} is VALID [2022-04-15 09:13:43,736 INFO L290 TraceCheckUtils]: 42: Hoare triple {1046#false} assume !false; {1046#false} is VALID [2022-04-15 09:13:43,736 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-04-15 09:13:43,737 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-15 09:13:54,981 INFO L290 TraceCheckUtils]: 42: Hoare triple {1046#false} assume !false; {1046#false} is VALID [2022-04-15 09:13:54,981 INFO L290 TraceCheckUtils]: 41: Hoare triple {1176#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1046#false} is VALID [2022-04-15 09:13:54,982 INFO L290 TraceCheckUtils]: 40: Hoare triple {1172#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1176#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:13:54,983 INFO L272 TraceCheckUtils]: 39: Hoare triple {1192#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1172#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:13:54,983 INFO L290 TraceCheckUtils]: 38: Hoare triple {1192#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} assume !false; {1192#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} is VALID [2022-04-15 09:13:55,076 INFO L290 TraceCheckUtils]: 37: Hoare triple {1199#(= (+ (* main_~z~0 main_~x~0) main_~a~0 (* main_~az~0 (* main_~z~0 main_~y~0))) (+ main_~a~0 (* main_~z~0 (+ (* main_~z~0 main_~x~0) main_~a~0))))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1192#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} is VALID [2022-04-15 09:13:55,080 INFO L284 TraceCheckUtils]: 36: Hoare quadruple {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} {1045#true} #61#return; {1199#(= (+ (* main_~z~0 main_~x~0) main_~a~0 (* main_~az~0 (* main_~z~0 main_~y~0))) (+ main_~a~0 (* main_~z~0 (+ (* main_~z~0 main_~x~0) main_~a~0))))} is VALID [2022-04-15 09:13:55,094 INFO L290 TraceCheckUtils]: 35: Hoare triple {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:13:55,094 INFO L290 TraceCheckUtils]: 34: Hoare triple {1212#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:13:55,095 INFO L290 TraceCheckUtils]: 33: Hoare triple {1045#true} ~cond := #in~cond; {1212#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 09:13:55,095 INFO L272 TraceCheckUtils]: 32: Hoare triple {1045#true} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1045#true} is VALID [2022-04-15 09:13:55,095 INFO L290 TraceCheckUtils]: 31: Hoare triple {1045#true} assume !false; {1045#true} is VALID [2022-04-15 09:13:55,095 INFO L290 TraceCheckUtils]: 30: Hoare triple {1045#true} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1045#true} is VALID [2022-04-15 09:13:55,095 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {1045#true} {1045#true} #61#return; {1045#true} is VALID [2022-04-15 09:13:55,095 INFO L290 TraceCheckUtils]: 28: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-15 09:13:55,095 INFO L290 TraceCheckUtils]: 27: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-15 09:13:55,096 INFO L290 TraceCheckUtils]: 26: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-15 09:13:55,096 INFO L272 TraceCheckUtils]: 25: Hoare triple {1045#true} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1045#true} is VALID [2022-04-15 09:13:55,096 INFO L290 TraceCheckUtils]: 24: Hoare triple {1045#true} assume !false; {1045#true} is VALID [2022-04-15 09:13:55,096 INFO L290 TraceCheckUtils]: 23: Hoare triple {1045#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {1045#true} is VALID [2022-04-15 09:13:55,096 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1045#true} {1045#true} #59#return; {1045#true} is VALID [2022-04-15 09:13:55,096 INFO L290 TraceCheckUtils]: 21: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-15 09:13:55,096 INFO L290 TraceCheckUtils]: 20: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-15 09:13:55,096 INFO L290 TraceCheckUtils]: 19: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-15 09:13:55,097 INFO L272 TraceCheckUtils]: 18: Hoare triple {1045#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 50 then 1 else 0)); {1045#true} is VALID [2022-04-15 09:13:55,097 INFO L290 TraceCheckUtils]: 17: Hoare triple {1045#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {1045#true} is VALID [2022-04-15 09:13:55,097 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1045#true} {1045#true} #57#return; {1045#true} is VALID [2022-04-15 09:13:55,097 INFO L290 TraceCheckUtils]: 15: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-15 09:13:55,097 INFO L290 TraceCheckUtils]: 14: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-15 09:13:55,097 INFO L290 TraceCheckUtils]: 13: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-15 09:13:55,097 INFO L272 TraceCheckUtils]: 12: Hoare triple {1045#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 50 then 1 else 0)); {1045#true} is VALID [2022-04-15 09:13:55,097 INFO L290 TraceCheckUtils]: 11: Hoare triple {1045#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {1045#true} is VALID [2022-04-15 09:13:55,098 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1045#true} {1045#true} #55#return; {1045#true} is VALID [2022-04-15 09:13:55,098 INFO L290 TraceCheckUtils]: 9: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-15 09:13:55,098 INFO L290 TraceCheckUtils]: 8: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-15 09:13:55,098 INFO L290 TraceCheckUtils]: 7: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-15 09:13:55,098 INFO L272 TraceCheckUtils]: 6: Hoare triple {1045#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 50 then 1 else 0)); {1045#true} is VALID [2022-04-15 09:13:55,098 INFO L290 TraceCheckUtils]: 5: Hoare triple {1045#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {1045#true} is VALID [2022-04-15 09:13:55,098 INFO L272 TraceCheckUtils]: 4: Hoare triple {1045#true} call #t~ret7 := main(); {1045#true} is VALID [2022-04-15 09:13:55,098 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1045#true} {1045#true} #65#return; {1045#true} is VALID [2022-04-15 09:13:55,099 INFO L290 TraceCheckUtils]: 2: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-15 09:13:55,099 INFO L290 TraceCheckUtils]: 1: Hoare triple {1045#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); {1045#true} is VALID [2022-04-15 09:13:55,099 INFO L272 TraceCheckUtils]: 0: Hoare triple {1045#true} call ULTIMATE.init(); {1045#true} is VALID [2022-04-15 09:13:55,099 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-04-15 09:13:55,099 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 09:13:55,099 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1668488059] [2022-04-15 09:13:55,099 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 09:13:55,100 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [446000941] [2022-04-15 09:13:55,100 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [446000941] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-15 09:13:55,100 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-15 09:13:55,100 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-04-15 09:13:55,100 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 09:13:55,100 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1125160443] [2022-04-15 09:13:55,100 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1125160443] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:13:55,100 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:13:55,100 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-15 09:13:55,100 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1030262956] [2022-04-15 09:13:55,100 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 09:13:55,101 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 43 [2022-04-15 09:13:55,101 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 09:13:55,101 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-15 09:13:55,151 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 34 edges. 34 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:13:55,152 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-15 09:13:55,152 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 09:13:55,152 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-15 09:13:55,152 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2022-04-15 09:13:55,153 INFO L87 Difference]: Start difference. First operand 40 states and 43 transitions. Second operand has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-15 09:13:55,764 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:13:55,764 INFO L93 Difference]: Finished difference Result 50 states and 54 transitions. [2022-04-15 09:13:55,764 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-15 09:13:55,764 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 43 [2022-04-15 09:13:55,765 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 09:13:55,765 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-15 09:13:55,766 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 48 transitions. [2022-04-15 09:13:55,766 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-15 09:13:55,768 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 48 transitions. [2022-04-15 09:13:55,768 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 9 states and 48 transitions. [2022-04-15 09:13:55,866 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 48 edges. 48 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:13:55,867 INFO L225 Difference]: With dead ends: 50 [2022-04-15 09:13:55,867 INFO L226 Difference]: Without dead ends: 47 [2022-04-15 09:13:55,868 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 74 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=45, Invalid=137, Unknown=0, NotChecked=0, Total=182 [2022-04-15 09:13:55,868 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 12 mSDsluCounter, 147 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 175 SdHoareTripleChecker+Invalid, 113 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-15 09:13:55,869 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 175 Invalid, 113 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-15 09:13:55,869 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2022-04-15 09:13:55,886 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2022-04-15 09:13:55,886 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 09:13:55,887 INFO L82 GeneralOperation]: Start isEquivalent. First operand 47 states. Second operand has 47 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 10 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 09:13:55,887 INFO L74 IsIncluded]: Start isIncluded. First operand 47 states. Second operand has 47 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 10 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 09:13:55,887 INFO L87 Difference]: Start difference. First operand 47 states. Second operand has 47 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 10 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 09:13:55,890 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:13:55,890 INFO L93 Difference]: Finished difference Result 47 states and 50 transitions. [2022-04-15 09:13:55,890 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 50 transitions. [2022-04-15 09:13:55,890 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:13:55,890 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:13:55,890 INFO L74 IsIncluded]: Start isIncluded. First operand has 47 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 10 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 47 states. [2022-04-15 09:13:55,891 INFO L87 Difference]: Start difference. First operand has 47 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 10 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 47 states. [2022-04-15 09:13:55,894 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:13:55,894 INFO L93 Difference]: Finished difference Result 47 states and 50 transitions. [2022-04-15 09:13:55,894 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 50 transitions. [2022-04-15 09:13:55,894 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:13:55,894 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:13:55,894 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 09:13:55,894 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 09:13:55,895 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 10 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 09:13:55,896 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 50 transitions. [2022-04-15 09:13:55,896 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 50 transitions. Word has length 43 [2022-04-15 09:13:55,896 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 09:13:55,897 INFO L478 AbstractCegarLoop]: Abstraction has 47 states and 50 transitions. [2022-04-15 09:13:55,897 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-15 09:13:55,897 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 47 states and 50 transitions. [2022-04-15 09:13:56,088 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 50 edges. 50 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:13:56,089 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 50 transitions. [2022-04-15 09:13:56,089 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-04-15 09:13:56,089 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 09:13:56,090 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 09:13:56,108 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-15 09:13:56,290 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:13:56,290 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 09:13:56,291 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 09:13:56,291 INFO L85 PathProgramCache]: Analyzing trace with hash 1099019754, now seen corresponding path program 5 times [2022-04-15 09:13:56,291 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 09:13:56,291 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1509888486] [2022-04-15 09:13:56,291 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 09:13:56,291 INFO L85 PathProgramCache]: Analyzing trace with hash 1099019754, now seen corresponding path program 6 times [2022-04-15 09:13:56,291 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 09:13:56,292 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1511138235] [2022-04-15 09:13:56,292 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 09:13:56,292 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 09:13:56,313 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 09:13:56,314 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1536187670] [2022-04-15 09:13:56,314 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-15 09:13:56,314 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:13:56,314 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 09:13:56,318 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 09:13:56,320 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-15 09:13:57,141 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2022-04-15 09:13:57,141 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 09:13:57,143 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 24 conjunts are in the unsatisfiable core [2022-04-15 09:13:57,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 09:13:57,179 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 09:14:06,600 WARN L914 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-15 09:14:09,302 WARN L914 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-15 09:14:17,674 WARN L914 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-15 09:14:36,371 WARN L232 SmtUtils]: Spent 6.52s on a formula simplification. DAG size of input: 46 DAG size of output: 38 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-15 09:14:50,666 INFO L272 TraceCheckUtils]: 0: Hoare triple {1606#true} call ULTIMATE.init(); {1606#true} is VALID [2022-04-15 09:14:50,666 INFO L290 TraceCheckUtils]: 1: Hoare triple {1606#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); {1606#true} is VALID [2022-04-15 09:14:50,666 INFO L290 TraceCheckUtils]: 2: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-15 09:14:50,666 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1606#true} {1606#true} #65#return; {1606#true} is VALID [2022-04-15 09:14:50,667 INFO L272 TraceCheckUtils]: 4: Hoare triple {1606#true} call #t~ret7 := main(); {1606#true} is VALID [2022-04-15 09:14:50,667 INFO L290 TraceCheckUtils]: 5: Hoare triple {1606#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {1606#true} is VALID [2022-04-15 09:14:50,667 INFO L272 TraceCheckUtils]: 6: Hoare triple {1606#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 50 then 1 else 0)); {1606#true} is VALID [2022-04-15 09:14:50,667 INFO L290 TraceCheckUtils]: 7: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-15 09:14:50,667 INFO L290 TraceCheckUtils]: 8: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-15 09:14:50,667 INFO L290 TraceCheckUtils]: 9: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-15 09:14:50,667 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1606#true} {1606#true} #55#return; {1606#true} is VALID [2022-04-15 09:14:50,667 INFO L290 TraceCheckUtils]: 11: Hoare triple {1606#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {1606#true} is VALID [2022-04-15 09:14:50,668 INFO L272 TraceCheckUtils]: 12: Hoare triple {1606#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 50 then 1 else 0)); {1606#true} is VALID [2022-04-15 09:14:50,668 INFO L290 TraceCheckUtils]: 13: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-15 09:14:50,668 INFO L290 TraceCheckUtils]: 14: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-15 09:14:50,668 INFO L290 TraceCheckUtils]: 15: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-15 09:14:50,668 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1606#true} {1606#true} #57#return; {1606#true} is VALID [2022-04-15 09:14:50,668 INFO L290 TraceCheckUtils]: 17: Hoare triple {1606#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {1606#true} is VALID [2022-04-15 09:14:50,668 INFO L272 TraceCheckUtils]: 18: Hoare triple {1606#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 50 then 1 else 0)); {1606#true} is VALID [2022-04-15 09:14:50,668 INFO L290 TraceCheckUtils]: 19: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-15 09:14:50,669 INFO L290 TraceCheckUtils]: 20: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-15 09:14:50,669 INFO L290 TraceCheckUtils]: 21: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-15 09:14:50,669 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1606#true} {1606#true} #59#return; {1606#true} is VALID [2022-04-15 09:14:50,670 INFO L290 TraceCheckUtils]: 23: Hoare triple {1606#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:14:50,673 INFO L290 TraceCheckUtils]: 24: Hoare triple {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:14:50,673 INFO L272 TraceCheckUtils]: 25: Hoare triple {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1606#true} is VALID [2022-04-15 09:14:50,674 INFO L290 TraceCheckUtils]: 26: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-15 09:14:50,674 INFO L290 TraceCheckUtils]: 27: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-15 09:14:50,674 INFO L290 TraceCheckUtils]: 28: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-15 09:14:50,675 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {1606#true} {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} #61#return; {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:14:50,675 INFO L290 TraceCheckUtils]: 30: Hoare triple {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} is VALID [2022-04-15 09:14:50,675 INFO L290 TraceCheckUtils]: 31: Hoare triple {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} assume !false; {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} is VALID [2022-04-15 09:14:50,675 INFO L272 TraceCheckUtils]: 32: Hoare triple {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1606#true} is VALID [2022-04-15 09:14:50,676 INFO L290 TraceCheckUtils]: 33: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-15 09:14:50,676 INFO L290 TraceCheckUtils]: 34: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-15 09:14:50,676 INFO L290 TraceCheckUtils]: 35: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-15 09:14:50,676 INFO L284 TraceCheckUtils]: 36: Hoare quadruple {1606#true} {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} #61#return; {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} is VALID [2022-04-15 09:14:50,677 INFO L290 TraceCheckUtils]: 37: Hoare triple {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} is VALID [2022-04-15 09:14:50,677 INFO L290 TraceCheckUtils]: 38: Hoare triple {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} assume !false; {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} is VALID [2022-04-15 09:14:50,677 INFO L272 TraceCheckUtils]: 39: Hoare triple {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1606#true} is VALID [2022-04-15 09:14:50,677 INFO L290 TraceCheckUtils]: 40: Hoare triple {1606#true} ~cond := #in~cond; {1733#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:14:50,678 INFO L290 TraceCheckUtils]: 41: Hoare triple {1733#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:14:50,679 INFO L290 TraceCheckUtils]: 42: Hoare triple {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:14:50,680 INFO L284 TraceCheckUtils]: 43: Hoare quadruple {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} #61#return; {1744#(and (= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:14:52,682 WARN L290 TraceCheckUtils]: 44: Hoare triple {1744#(and (= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1748#(and (or (and (= 0 (mod (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) (or (and (= (mod main_~y~0 main_~z~0) 0) (= (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) (+ main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0))) (= main_~az~0 0)) (and (= (mod (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) 0) (not (= main_~az~0 0)) (= (* (div (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) main_~z~0) main_~y~0))) (not (= main_~z~0 0))) (and (= main_~z~0 0) (= main_~y~0 0) (= main_~a~0 main_~x~0))) (= (* main_~a~0 main_~z~0) main_~az~0))} is UNKNOWN [2022-04-15 09:14:52,683 INFO L290 TraceCheckUtils]: 45: Hoare triple {1748#(and (or (and (= 0 (mod (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) (or (and (= (mod main_~y~0 main_~z~0) 0) (= (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) (+ main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0))) (= main_~az~0 0)) (and (= (mod (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) 0) (not (= main_~az~0 0)) (= (* (div (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) main_~z~0) main_~y~0))) (not (= main_~z~0 0))) (and (= main_~z~0 0) (= main_~y~0 0) (= main_~a~0 main_~x~0))) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {1748#(and (or (and (= 0 (mod (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) (or (and (= (mod main_~y~0 main_~z~0) 0) (= (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) (+ main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0))) (= main_~az~0 0)) (and (= (mod (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) 0) (not (= main_~az~0 0)) (= (* (div (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) main_~z~0) main_~y~0))) (not (= main_~z~0 0))) (and (= main_~z~0 0) (= main_~y~0 0) (= main_~a~0 main_~x~0))) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-15 09:14:53,034 INFO L272 TraceCheckUtils]: 46: Hoare triple {1748#(and (or (and (= 0 (mod (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) (or (and (= (mod main_~y~0 main_~z~0) 0) (= (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) (+ main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0))) (= main_~az~0 0)) (and (= (mod (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) 0) (not (= main_~az~0 0)) (= (* (div (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) main_~z~0) main_~y~0))) (not (= main_~z~0 0))) (and (= main_~z~0 0) (= main_~y~0 0) (= main_~a~0 main_~x~0))) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1755#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:14:53,035 INFO L290 TraceCheckUtils]: 47: Hoare triple {1755#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1759#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:14:53,035 INFO L290 TraceCheckUtils]: 48: Hoare triple {1759#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1607#false} is VALID [2022-04-15 09:14:53,035 INFO L290 TraceCheckUtils]: 49: Hoare triple {1607#false} assume !false; {1607#false} is VALID [2022-04-15 09:14:53,036 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2022-04-15 09:14:53,036 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-15 09:15:29,963 INFO L290 TraceCheckUtils]: 49: Hoare triple {1607#false} assume !false; {1607#false} is VALID [2022-04-15 09:15:29,964 INFO L290 TraceCheckUtils]: 48: Hoare triple {1759#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1607#false} is VALID [2022-04-15 09:15:29,964 INFO L290 TraceCheckUtils]: 47: Hoare triple {1755#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1759#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 09:15:29,965 INFO L272 TraceCheckUtils]: 46: Hoare triple {1775#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1755#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 09:15:29,965 INFO L290 TraceCheckUtils]: 45: Hoare triple {1775#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} assume !false; {1775#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} is VALID [2022-04-15 09:15:29,981 INFO L290 TraceCheckUtils]: 44: Hoare triple {1782#(= (+ (* main_~z~0 main_~x~0) main_~a~0 (* main_~az~0 (* main_~z~0 main_~y~0))) (+ main_~a~0 (* main_~z~0 (+ (* main_~z~0 main_~x~0) main_~a~0))))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1775#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} is VALID [2022-04-15 09:15:29,984 INFO L284 TraceCheckUtils]: 43: Hoare quadruple {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} {1606#true} #61#return; {1782#(= (+ (* main_~z~0 main_~x~0) main_~a~0 (* main_~az~0 (* main_~z~0 main_~y~0))) (+ main_~a~0 (* main_~z~0 (+ (* main_~z~0 main_~x~0) main_~a~0))))} is VALID [2022-04-15 09:15:29,984 INFO L290 TraceCheckUtils]: 42: Hoare triple {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:15:29,984 INFO L290 TraceCheckUtils]: 41: Hoare triple {1795#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 09:15:29,985 INFO L290 TraceCheckUtils]: 40: Hoare triple {1606#true} ~cond := #in~cond; {1795#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 09:15:29,985 INFO L272 TraceCheckUtils]: 39: Hoare triple {1606#true} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1606#true} is VALID [2022-04-15 09:15:29,985 INFO L290 TraceCheckUtils]: 38: Hoare triple {1606#true} assume !false; {1606#true} is VALID [2022-04-15 09:15:29,985 INFO L290 TraceCheckUtils]: 37: Hoare triple {1606#true} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1606#true} is VALID [2022-04-15 09:15:29,985 INFO L284 TraceCheckUtils]: 36: Hoare quadruple {1606#true} {1606#true} #61#return; {1606#true} is VALID [2022-04-15 09:15:29,985 INFO L290 TraceCheckUtils]: 35: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-15 09:15:29,985 INFO L290 TraceCheckUtils]: 34: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-15 09:15:29,985 INFO L290 TraceCheckUtils]: 33: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-15 09:15:29,985 INFO L272 TraceCheckUtils]: 32: Hoare triple {1606#true} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1606#true} is VALID [2022-04-15 09:15:29,986 INFO L290 TraceCheckUtils]: 31: Hoare triple {1606#true} assume !false; {1606#true} is VALID [2022-04-15 09:15:29,986 INFO L290 TraceCheckUtils]: 30: Hoare triple {1606#true} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1606#true} is VALID [2022-04-15 09:15:29,986 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {1606#true} {1606#true} #61#return; {1606#true} is VALID [2022-04-15 09:15:29,986 INFO L290 TraceCheckUtils]: 28: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-15 09:15:29,986 INFO L290 TraceCheckUtils]: 27: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-15 09:15:29,986 INFO L290 TraceCheckUtils]: 26: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-15 09:15:29,986 INFO L272 TraceCheckUtils]: 25: Hoare triple {1606#true} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1606#true} is VALID [2022-04-15 09:15:29,986 INFO L290 TraceCheckUtils]: 24: Hoare triple {1606#true} assume !false; {1606#true} is VALID [2022-04-15 09:15:29,986 INFO L290 TraceCheckUtils]: 23: Hoare triple {1606#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {1606#true} is VALID [2022-04-15 09:15:29,987 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1606#true} {1606#true} #59#return; {1606#true} is VALID [2022-04-15 09:15:29,987 INFO L290 TraceCheckUtils]: 21: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-15 09:15:29,987 INFO L290 TraceCheckUtils]: 20: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-15 09:15:29,987 INFO L290 TraceCheckUtils]: 19: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-15 09:15:29,987 INFO L272 TraceCheckUtils]: 18: Hoare triple {1606#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 50 then 1 else 0)); {1606#true} is VALID [2022-04-15 09:15:29,987 INFO L290 TraceCheckUtils]: 17: Hoare triple {1606#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {1606#true} is VALID [2022-04-15 09:15:29,987 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1606#true} {1606#true} #57#return; {1606#true} is VALID [2022-04-15 09:15:29,987 INFO L290 TraceCheckUtils]: 15: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-15 09:15:29,987 INFO L290 TraceCheckUtils]: 14: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-15 09:15:29,987 INFO L290 TraceCheckUtils]: 13: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-15 09:15:29,988 INFO L272 TraceCheckUtils]: 12: Hoare triple {1606#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 50 then 1 else 0)); {1606#true} is VALID [2022-04-15 09:15:29,988 INFO L290 TraceCheckUtils]: 11: Hoare triple {1606#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {1606#true} is VALID [2022-04-15 09:15:29,988 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1606#true} {1606#true} #55#return; {1606#true} is VALID [2022-04-15 09:15:29,988 INFO L290 TraceCheckUtils]: 9: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-15 09:15:29,988 INFO L290 TraceCheckUtils]: 8: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-15 09:15:29,988 INFO L290 TraceCheckUtils]: 7: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-15 09:15:29,988 INFO L272 TraceCheckUtils]: 6: Hoare triple {1606#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 50 then 1 else 0)); {1606#true} is VALID [2022-04-15 09:15:29,988 INFO L290 TraceCheckUtils]: 5: Hoare triple {1606#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {1606#true} is VALID [2022-04-15 09:15:29,988 INFO L272 TraceCheckUtils]: 4: Hoare triple {1606#true} call #t~ret7 := main(); {1606#true} is VALID [2022-04-15 09:15:29,988 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1606#true} {1606#true} #65#return; {1606#true} is VALID [2022-04-15 09:15:29,988 INFO L290 TraceCheckUtils]: 2: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-15 09:15:29,988 INFO L290 TraceCheckUtils]: 1: Hoare triple {1606#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); {1606#true} is VALID [2022-04-15 09:15:29,989 INFO L272 TraceCheckUtils]: 0: Hoare triple {1606#true} call ULTIMATE.init(); {1606#true} is VALID [2022-04-15 09:15:29,989 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 19 proven. 1 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2022-04-15 09:15:29,989 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 09:15:29,989 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1511138235] [2022-04-15 09:15:29,989 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 09:15:29,989 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1536187670] [2022-04-15 09:15:29,989 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1536187670] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-15 09:15:29,989 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-15 09:15:29,989 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 13 [2022-04-15 09:15:29,990 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 09:15:29,990 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1509888486] [2022-04-15 09:15:29,990 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1509888486] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 09:15:29,990 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 09:15:29,990 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-04-15 09:15:29,990 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [836280744] [2022-04-15 09:15:29,990 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 09:15:29,991 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) Word has length 50 [2022-04-15 09:15:29,991 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 09:15:29,991 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-15 09:15:32,047 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 39 edges. 38 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-15 09:15:32,047 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-15 09:15:32,047 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 09:15:32,047 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-15 09:15:32,047 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2022-04-15 09:15:32,048 INFO L87 Difference]: Start difference. First operand 47 states and 50 transitions. Second operand has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-15 09:15:38,341 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-15 09:15:40,344 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-15 09:15:42,984 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:15:42,984 INFO L93 Difference]: Finished difference Result 47 states and 50 transitions. [2022-04-15 09:15:42,984 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-15 09:15:42,984 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) Word has length 50 [2022-04-15 09:15:42,985 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 09:15:42,985 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-15 09:15:42,986 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 33 transitions. [2022-04-15 09:15:42,986 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-15 09:15:42,987 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 33 transitions. [2022-04-15 09:15:42,987 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 33 transitions. [2022-04-15 09:15:47,086 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 33 edges. 31 inductive. 0 not inductive. 2 times theorem prover too weak to decide inductivity. [2022-04-15 09:15:47,087 INFO L225 Difference]: With dead ends: 47 [2022-04-15 09:15:47,087 INFO L226 Difference]: Without dead ends: 0 [2022-04-15 09:15:47,087 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 87 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 36 ImplicationChecksByTransitivity, 6.7s TimeCoverageRelationStatistics Valid=46, Invalid=136, Unknown=0, NotChecked=0, Total=182 [2022-04-15 09:15:47,088 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 11 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 7 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.4s IncrementalHoareTripleChecker+Time [2022-04-15 09:15:47,088 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 126 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 40 Invalid, 2 Unknown, 0 Unchecked, 4.4s Time] [2022-04-15 09:15:47,089 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-15 09:15:47,089 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-15 09:15:47,089 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 09:15:47,089 INFO L82 GeneralOperation]: Start isEquivalent. First operand 0 states. Second operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-15 09:15:47,089 INFO L74 IsIncluded]: Start isIncluded. First operand 0 states. Second operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-15 09:15:47,089 INFO L87 Difference]: Start difference. First operand 0 states. Second operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-15 09:15:47,089 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:15:47,089 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-15 09:15:47,089 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-15 09:15:47,090 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:15:47,090 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:15:47,090 INFO L74 IsIncluded]: Start isIncluded. First operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand 0 states. [2022-04-15 09:15:47,090 INFO L87 Difference]: Start difference. First operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand 0 states. [2022-04-15 09:15:47,090 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 09:15:47,090 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-15 09:15:47,090 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-15 09:15:47,090 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:15:47,090 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 09:15:47,090 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 09:15:47,090 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 09:15:47,090 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-15 09:15:47,091 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-15 09:15:47,091 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 50 [2022-04-15 09:15:47,091 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 09:15:47,091 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-15 09:15:47,091 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-15 09:15:47,091 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 0 states and 0 transitions. [2022-04-15 09:15:47,091 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 0 edges. 0 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 09:15:47,091 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-15 09:15:47,091 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 09:15:47,093 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-15 09:15:47,102 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2022-04-15 09:15:47,299 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 09:15:47,301 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-04-15 09:16:22,684 WARN L232 SmtUtils]: Spent 35.35s on a formula simplification. DAG size of input: 53 DAG size of output: 43 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-15 09:16:58,958 WARN L232 SmtUtils]: Spent 36.27s on a formula simplification. DAG size of input: 53 DAG size of output: 43 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-15 09:18:07,316 WARN L232 SmtUtils]: Spent 1.14m on a formula simplification. DAG size of input: 53 DAG size of output: 50 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-15 09:18:17,580 WARN L232 SmtUtils]: Spent 10.23s on a formula simplification. DAG size of input: 53 DAG size of output: 43 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-15 09:18:17,638 INFO L882 garLoopResultBuilder]: For program point reach_errorEXIT(line 8) no Hoare annotation was computed. [2022-04-15 09:18:17,638 INFO L882 garLoopResultBuilder]: For program point reach_errorENTRY(line 8) no Hoare annotation was computed. [2022-04-15 09:18:17,638 INFO L882 garLoopResultBuilder]: For program point reach_errorFINAL(line 8) no Hoare annotation was computed. [2022-04-15 09:18:17,638 INFO L885 garLoopResultBuilder]: At program point assume_abort_if_notENTRY(lines 11 13) the Hoare annotation is: true [2022-04-15 09:18:17,638 INFO L878 garLoopResultBuilder]: At program point L12(line 12) the Hoare annotation is: (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|) [2022-04-15 09:18:17,638 INFO L878 garLoopResultBuilder]: At program point L12-2(lines 11 13) the Hoare annotation is: (and (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)) [2022-04-15 09:18:17,638 INFO L878 garLoopResultBuilder]: At program point assume_abort_if_notEXIT(lines 11 13) the Hoare annotation is: (and (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)) [2022-04-15 09:18:17,639 INFO L885 garLoopResultBuilder]: At program point L29(line 29) the Hoare annotation is: true [2022-04-15 09:18:17,639 INFO L885 garLoopResultBuilder]: At program point L29-1(line 29) the Hoare annotation is: true [2022-04-15 09:18:17,639 INFO L885 garLoopResultBuilder]: At program point L27(line 27) the Hoare annotation is: true [2022-04-15 09:18:17,639 INFO L885 garLoopResultBuilder]: At program point L27-1(line 27) the Hoare annotation is: true [2022-04-15 09:18:17,639 INFO L885 garLoopResultBuilder]: At program point L25(line 25) the Hoare annotation is: true [2022-04-15 09:18:17,639 INFO L885 garLoopResultBuilder]: At program point mainEXIT(lines 21 48) the Hoare annotation is: true [2022-04-15 09:18:17,639 INFO L885 garLoopResultBuilder]: At program point L25-1(line 25) the Hoare annotation is: true [2022-04-15 09:18:17,639 INFO L885 garLoopResultBuilder]: At program point L46(line 46) the Hoare annotation is: true [2022-04-15 09:18:17,639 INFO L885 garLoopResultBuilder]: At program point mainFINAL(lines 21 48) the Hoare annotation is: true [2022-04-15 09:18:17,639 INFO L878 garLoopResultBuilder]: At program point L36-2(lines 36 45) the Hoare annotation is: (let ((.cse0 (= main_~a~0 main_~x~0)) (.cse1 (= (* main_~a~0 main_~z~0) main_~az~0))) (or (and (= main_~y~0 1) .cse0 .cse1) (and (let ((.cse7 (= main_~z~0 0))) (or (let ((.cse2 (+ (* (- 1) main_~a~0) main_~x~0))) (and (= 0 (mod .cse2 main_~z~0)) (let ((.cse3 (div .cse2 main_~z~0))) (let ((.cse5 (= main_~az~0 0)) (.cse4 (* .cse3 main_~z~0))) (or (and (= (mod main_~y~0 main_~z~0) 0) (= .cse3 (+ main_~a~0 .cse4)) .cse5) (let ((.cse6 (+ (* (- 1) .cse3) main_~a~0 .cse4))) (and (= (mod .cse6 main_~az~0) 0) (not .cse5) (= (* (div .cse6 main_~az~0) main_~z~0) main_~y~0)))))) (not .cse7))) (and .cse7 (= main_~y~0 0) .cse0))) .cse1))) [2022-04-15 09:18:17,639 INFO L878 garLoopResultBuilder]: At program point L36-3(lines 36 45) the Hoare annotation is: (let ((.cse1 (* main_~a~0 main_~z~0))) (let ((.cse0 (= .cse1 main_~az~0))) (or (and (= main_~y~0 1) (= main_~a~0 main_~x~0) .cse0) (and (= main_~x~0 (+ .cse1 main_~a~0 (* main_~a~0 main_~z~0 main_~z~0))) (= (* main_~z~0 main_~z~0) main_~y~0) .cse0) (let ((.cse2 (+ (* (- 1) main_~a~0) main_~x~0))) (and (= 0 (mod .cse2 main_~z~0)) (let ((.cse3 (div .cse2 main_~z~0))) (let ((.cse5 (= main_~az~0 0)) (.cse4 (* .cse3 main_~z~0))) (or (and (= (mod main_~y~0 main_~z~0) 0) (= .cse3 (+ main_~a~0 .cse4)) .cse5) (let ((.cse6 (+ (* (- 1) .cse3) main_~a~0 .cse4))) (and (= (mod .cse6 main_~az~0) 0) (not .cse5) (= (* (div .cse6 main_~az~0) main_~z~0) main_~y~0)))))) (not (= main_~z~0 0)) .cse0)) (and (= main_~z~0 main_~y~0) (= main_~x~0 (+ .cse1 main_~a~0)) .cse0)))) [2022-04-15 09:18:17,639 INFO L885 garLoopResultBuilder]: At program point mainENTRY(lines 21 48) the Hoare annotation is: true [2022-04-15 09:18:17,640 INFO L878 garLoopResultBuilder]: At program point L37(line 37) the Hoare annotation is: (let ((.cse0 (= main_~a~0 main_~x~0)) (.cse1 (= (* main_~a~0 main_~z~0) main_~az~0))) (or (and (= main_~y~0 1) .cse0 .cse1) (and (let ((.cse7 (= main_~z~0 0))) (or (let ((.cse2 (+ (* (- 1) main_~a~0) main_~x~0))) (and (= 0 (mod .cse2 main_~z~0)) (let ((.cse3 (div .cse2 main_~z~0))) (let ((.cse5 (= main_~az~0 0)) (.cse4 (* .cse3 main_~z~0))) (or (and (= (mod main_~y~0 main_~z~0) 0) (= .cse3 (+ main_~a~0 .cse4)) .cse5) (let ((.cse6 (+ (* (- 1) .cse3) main_~a~0 .cse4))) (and (= (mod .cse6 main_~az~0) 0) (not .cse5) (= (* (div .cse6 main_~az~0) main_~z~0) main_~y~0)))))) (not .cse7))) (and .cse7 (= main_~y~0 0) .cse0))) .cse1))) [2022-04-15 09:18:17,640 INFO L878 garLoopResultBuilder]: At program point L37-1(lines 36 45) the Hoare annotation is: (let ((.cse0 (= main_~a~0 main_~x~0)) (.cse1 (= (* main_~a~0 main_~z~0) main_~az~0))) (or (and (= main_~y~0 1) .cse0 .cse1) (and (let ((.cse7 (= main_~z~0 0))) (or (let ((.cse2 (+ (* (- 1) main_~a~0) main_~x~0))) (and (= 0 (mod .cse2 main_~z~0)) (let ((.cse3 (div .cse2 main_~z~0))) (let ((.cse5 (= main_~az~0 0)) (.cse4 (* .cse3 main_~z~0))) (or (and (= (mod main_~y~0 main_~z~0) 0) (= .cse3 (+ main_~a~0 .cse4)) .cse5) (let ((.cse6 (+ (* (- 1) .cse3) main_~a~0 .cse4))) (and (= (mod .cse6 main_~az~0) 0) (not .cse5) (= (* (div .cse6 main_~az~0) main_~z~0) main_~y~0)))))) (not .cse7))) (and .cse7 (= main_~y~0 0) .cse0))) .cse1))) [2022-04-15 09:18:17,640 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.initFINAL(line -1) the Hoare annotation is: true [2022-04-15 09:18:17,640 INFO L878 garLoopResultBuilder]: At program point ULTIMATE.initENTRY(line -1) the Hoare annotation is: (and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|)) [2022-04-15 09:18:17,640 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.initEXIT(line -1) the Hoare annotation is: true [2022-04-15 09:18:17,640 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startEXIT(line -1) the Hoare annotation is: true [2022-04-15 09:18:17,640 INFO L885 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-04-15 09:18:17,640 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-04-15 09:18:17,640 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startFINAL(line -1) the Hoare annotation is: true [2022-04-15 09:18:17,640 INFO L878 garLoopResultBuilder]: At program point L16(lines 16 17) the Hoare annotation is: (not (<= 1 |__VERIFIER_assert_#in~cond|)) [2022-04-15 09:18:17,640 INFO L878 garLoopResultBuilder]: At program point L15(lines 15 18) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-15 09:18:17,640 INFO L885 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 14 20) the Hoare annotation is: true [2022-04-15 09:18:17,641 INFO L878 garLoopResultBuilder]: At program point L15-2(lines 14 20) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-15 09:18:17,641 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertEXIT(lines 14 20) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-15 09:18:17,641 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 17) the Hoare annotation is: (not (<= 1 |__VERIFIER_assert_#in~cond|)) [2022-04-15 09:18:17,643 INFO L719 BasicCegarLoop]: Path program histogram: [6, 2, 2] [2022-04-15 09:18:17,644 INFO L177 ceAbstractionStarter]: Computing trace abstraction results [2022-04-15 09:18:17,648 WARN L170 areAnnotationChecker]: reach_errorENTRY has no Hoare annotation [2022-04-15 09:18:17,652 WARN L170 areAnnotationChecker]: reach_errorFINAL has no Hoare annotation [2022-04-15 09:18:19,667 INFO L163 areAnnotationChecker]: CFG has 38 edges. 37 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. 0 times interpolants missing. [2022-04-15 09:18:19,676 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 15.04 09:18:19 BoogieIcfgContainer [2022-04-15 09:18:19,676 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-15 09:18:19,677 INFO L158 Benchmark]: Toolchain (without parser) took 296984.70ms. Allocated memory was 204.5MB in the beginning and 248.5MB in the end (delta: 44.0MB). Free memory was 156.1MB in the beginning and 109.6MB in the end (delta: 46.4MB). Peak memory consumption was 90.1MB. Max. memory is 8.0GB. [2022-04-15 09:18:19,677 INFO L158 Benchmark]: CDTParser took 0.11ms. Allocated memory is still 204.5MB. Free memory was 172.0MB in the beginning and 171.8MB in the end (delta: 151.8kB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-15 09:18:19,678 INFO L158 Benchmark]: CACSL2BoogieTranslator took 201.36ms. Allocated memory is still 204.5MB. Free memory was 155.8MB in the beginning and 179.8MB in the end (delta: -24.0MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2022-04-15 09:18:19,678 INFO L158 Benchmark]: Boogie Preprocessor took 23.68ms. Allocated memory is still 204.5MB. Free memory was 179.8MB in the beginning and 178.3MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-15 09:18:19,678 INFO L158 Benchmark]: RCFGBuilder took 335.62ms. Allocated memory is still 204.5MB. Free memory was 178.3MB in the beginning and 166.8MB in the end (delta: 11.5MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-15 09:18:19,678 INFO L158 Benchmark]: TraceAbstraction took 296417.69ms. Allocated memory was 204.5MB in the beginning and 248.5MB in the end (delta: 44.0MB). Free memory was 166.2MB in the beginning and 109.6MB in the end (delta: 56.6MB). Peak memory consumption was 101.0MB. Max. memory is 8.0GB. [2022-04-15 09:18:19,680 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - AssertionsEnabledResult: Assertions are enabled Assertions are enabled - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.11ms. Allocated memory is still 204.5MB. Free memory was 172.0MB in the beginning and 171.8MB in the end (delta: 151.8kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 201.36ms. Allocated memory is still 204.5MB. Free memory was 155.8MB in the beginning and 179.8MB in the end (delta: -24.0MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * Boogie Preprocessor took 23.68ms. Allocated memory is still 204.5MB. Free memory was 179.8MB in the beginning and 178.3MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 335.62ms. Allocated memory is still 204.5MB. Free memory was 178.3MB in the beginning and 166.8MB in the end (delta: 11.5MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * TraceAbstraction took 296417.69ms. Allocated memory was 204.5MB in the beginning and 248.5MB in the end (delta: 44.0MB). Free memory was 166.2MB in the beginning and 109.6MB in the end (delta: 56.6MB). Peak memory consumption was 101.0MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 17]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 34 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 294.3s, OverallIterations: 5, TraceHistogramMax: 4, PathProgramHistogramMax: 6, EmptinessCheckTime: 0.0s, AutomataDifference: 17.5s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 150.3s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 2 mSolverCounterUnknown, 69 SdHoareTripleChecker+Valid, 5.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 60 mSDsluCounter, 575 SdHoareTripleChecker+Invalid, 5.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 445 mSDsCounter, 21 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 318 IncrementalHoareTripleChecker+Invalid, 341 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 21 mSolverCounterUnsat, 130 mSDtfsCounter, 318 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 303 GetRequests, 257 SyntacticMatches, 3 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 7.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=47occurred in iteration=4, InterpolantAutomatonStates: 33, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 5 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 31 LocationsWithAnnotation, 101 PreInvPairs, 161 NumberOfFragments, 614 HoareAnnotationTreeSize, 101 FomulaSimplifications, 0 FormulaSimplificationTreeSizeReduction, 0.0s HoareSimplificationTime, 31 FomulaSimplificationsInter, 884 FormulaSimplificationTreeSizeReductionInter, 150.3s HoareSimplificationTimeInter, 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 - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 36]: Loop Invariant Derived loop invariant: ((y == 1 && a == x) && a * z == az) || ((((0 == (-1 * a + x) % z && (((y % z == 0 && (-1 * a + x) / z == a + (-1 * a + x) / z * z) && az == 0) || (((-1 * ((-1 * a + x) / z) + a + (-1 * a + x) / z * z) % az == 0 && !(az == 0)) && (-1 * ((-1 * a + x) / z) + a + (-1 * a + x) / z * z) / az * z == y))) && !(z == 0)) || ((z == 0 && y == 0) && a == x)) && a * z == az) - ProcedureContractResult [Line: 11]: Procedure Contract for assume_abort_if_not Derived contract for procedure assume_abort_if_not: !(\old(cond) == 0) && cond == \old(cond) - ProcedureContractResult [Line: 21]: Procedure Contract for main Derived contract for procedure main: 1 - ProcedureContractResult [Line: 14]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert: \old(cond) == cond || !(1 <= \old(cond)) RESULT: Ultimate proved your program to be correct! [2022-04-15 09:18:19,729 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...