/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/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/fermat1-ll_valuebound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-e106359-m [2022-04-15 15:13:33,436 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-15 15:13:33,438 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-15 15:13:33,485 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-15 15:13:33,485 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-15 15:13:33,486 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-15 15:13:33,488 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-15 15:13:33,490 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-15 15:13:33,491 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-15 15:13:33,494 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-15 15:13:33,495 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-15 15:13:33,496 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-15 15:13:33,496 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-15 15:13:33,498 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-15 15:13:33,499 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-15 15:13:33,501 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-15 15:13:33,501 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-15 15:13:33,501 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-15 15:13:33,503 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-15 15:13:33,507 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-15 15:13:33,508 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-15 15:13:33,509 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-15 15:13:33,509 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-15 15:13:33,510 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-15 15:13:33,511 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-15 15:13:33,515 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-15 15:13:33,515 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-15 15:13:33,515 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-15 15:13:33,516 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-15 15:13:33,516 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-15 15:13:33,517 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-15 15:13:33,517 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-15 15:13:33,518 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-15 15:13:33,518 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-15 15:13:33,519 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-15 15:13:33,519 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-15 15:13:33,519 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-15 15:13:33,520 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-15 15:13:33,520 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-15 15:13:33,520 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-15 15:13:33,520 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-15 15:13:33,521 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-15 15:13:33,522 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-15 15:13:33,530 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-15 15:13:33,530 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-15 15:13:33,531 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-15 15:13:33,531 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-15 15:13:33,531 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-15 15:13:33,531 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-15 15:13:33,531 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-15 15:13:33,531 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-15 15:13:33,531 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-15 15:13:33,532 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-15 15:13:33,532 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-15 15:13:33,532 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-15 15:13:33,532 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-15 15:13:33,532 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-15 15:13:33,532 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-15 15:13:33,532 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 15:13:33,533 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-15 15:13:33,533 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-15 15:13:33,533 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-15 15:13:33,533 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-15 15:13:33,533 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-15 15:13:33,533 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-15 15:13:33,533 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 15:13:33,718 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-15 15:13:33,737 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-15 15:13:33,739 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-15 15:13:33,740 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-15 15:13:33,740 INFO L275 PluginConnector]: CDTParser initialized [2022-04-15 15:13:33,741 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/fermat1-ll_valuebound5.c [2022-04-15 15:13:33,791 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/601c288e9/d5aa69d790514f41ae23bd5c99b68fb5/FLAGa2831d3a8 [2022-04-15 15:13:34,149 INFO L306 CDTParser]: Found 1 translation units. [2022-04-15 15:13:34,149 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/fermat1-ll_valuebound5.c [2022-04-15 15:13:34,154 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/601c288e9/d5aa69d790514f41ae23bd5c99b68fb5/FLAGa2831d3a8 [2022-04-15 15:13:34,162 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/601c288e9/d5aa69d790514f41ae23bd5c99b68fb5 [2022-04-15 15:13:34,163 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-15 15:13:34,164 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-15 15:13:34,165 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-15 15:13:34,165 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-15 15:13:34,167 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-15 15:13:34,168 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 03:13:34" (1/1) ... [2022-04-15 15:13:34,168 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@67490d09 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:13:34, skipping insertion in model container [2022-04-15 15:13:34,168 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 03:13:34" (1/1) ... [2022-04-15 15:13:34,172 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-15 15:13:34,180 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-15 15:13:34,285 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/fermat1-ll_valuebound5.c[535,548] [2022-04-15 15:13:34,301 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 15:13:34,312 INFO L203 MainTranslator]: Completed pre-run [2022-04-15 15:13:34,319 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/fermat1-ll_valuebound5.c[535,548] [2022-04-15 15:13:34,325 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 15:13:34,335 INFO L208 MainTranslator]: Completed translation [2022-04-15 15:13:34,335 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:13:34 WrapperNode [2022-04-15 15:13:34,335 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-15 15:13:34,336 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-15 15:13:34,336 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-15 15:13:34,336 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-15 15:13:34,343 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:13:34" (1/1) ... [2022-04-15 15:13:34,343 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:13:34" (1/1) ... [2022-04-15 15:13:34,352 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:13:34" (1/1) ... [2022-04-15 15:13:34,352 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:13:34" (1/1) ... [2022-04-15 15:13:34,361 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:13:34" (1/1) ... [2022-04-15 15:13:34,364 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:13:34" (1/1) ... [2022-04-15 15:13:34,365 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:13:34" (1/1) ... [2022-04-15 15:13:34,366 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-15 15:13:34,366 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-15 15:13:34,366 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-15 15:13:34,366 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-15 15:13:34,367 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:13:34" (1/1) ... [2022-04-15 15:13:34,376 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 15:13:34,383 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:13:34,391 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 15:13:34,414 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-15 15:13:34,414 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-15 15:13:34,414 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-15 15:13:34,414 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-15 15:13:34,414 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-15 15:13:34,414 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-15 15:13:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-15 15:13:34,404 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 15:13:34,462 INFO L234 CfgBuilder]: Building ICFG [2022-04-15 15:13:34,463 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-15 15:13:34,621 INFO L275 CfgBuilder]: Performing block encoding [2022-04-15 15:13:34,626 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-15 15:13:34,626 INFO L299 CfgBuilder]: Removed 3 assume(true) statements. [2022-04-15 15:13:34,627 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 03:13:34 BoogieIcfgContainer [2022-04-15 15:13:34,627 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-15 15:13:34,628 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-15 15:13:34,628 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-15 15:13:34,641 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-15 15:13:34,641 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.04 03:13:34" (1/3) ... [2022-04-15 15:13:34,642 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7a35b880 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 03:13:34, skipping insertion in model container [2022-04-15 15:13:34,642 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 03:13:34" (2/3) ... [2022-04-15 15:13:34,642 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7a35b880 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 03:13:34, skipping insertion in model container [2022-04-15 15:13:34,642 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 03:13:34" (3/3) ... [2022-04-15 15:13:34,643 INFO L111 eAbstractionObserver]: Analyzing ICFG fermat1-ll_valuebound5.c [2022-04-15 15:13:34,647 INFO L202 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-15 15:13:34,647 INFO L161 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-15 15:13:34,673 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-15 15:13:34,677 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 15:13:34,677 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-15 15:13:34,694 INFO L276 IsEmpty]: Start isEmpty. Operand has 37 states, 21 states have (on average 1.5714285714285714) internal successors, (33), 22 states have internal predecessors, (33), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-15 15:13:34,698 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-04-15 15:13:34,698 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:13:34,699 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:13:34,699 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:13:34,702 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:13:34,702 INFO L85 PathProgramCache]: Analyzing trace with hash -1718462925, now seen corresponding path program 1 times [2022-04-15 15:13:34,707 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:13:34,707 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [631257524] [2022-04-15 15:13:34,714 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:13:34,714 INFO L85 PathProgramCache]: Analyzing trace with hash -1718462925, now seen corresponding path program 2 times [2022-04-15 15:13:34,716 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:13:34,716 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [734035859] [2022-04-15 15:13:34,716 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:13:34,717 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:13:34,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:13:34,843 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 15:13:34,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:13:34,857 INFO L290 TraceCheckUtils]: 0: Hoare triple {61#(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(13, 2);call #Ultimate.allocInit(12, 3); {40#true} is VALID [2022-04-15 15:13:34,857 INFO L290 TraceCheckUtils]: 1: Hoare triple {40#true} assume true; {40#true} is VALID [2022-04-15 15:13:34,857 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {40#true} {40#true} #106#return; {40#true} is VALID [2022-04-15 15:13:34,858 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 15:13:34,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:13:34,869 INFO L290 TraceCheckUtils]: 0: Hoare triple {40#true} ~cond := #in~cond; {40#true} is VALID [2022-04-15 15:13:34,870 INFO L290 TraceCheckUtils]: 1: Hoare triple {40#true} assume 0 == ~cond;assume false; {41#false} is VALID [2022-04-15 15:13:34,870 INFO L290 TraceCheckUtils]: 2: Hoare triple {41#false} assume true; {41#false} is VALID [2022-04-15 15:13:34,870 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {41#false} {40#true} #90#return; {41#false} is VALID [2022-04-15 15:13:34,871 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-15 15:13:34,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:13:34,878 INFO L290 TraceCheckUtils]: 0: Hoare triple {40#true} ~cond := #in~cond; {40#true} is VALID [2022-04-15 15:13:34,878 INFO L290 TraceCheckUtils]: 1: Hoare triple {40#true} assume 0 == ~cond;assume false; {41#false} is VALID [2022-04-15 15:13:34,878 INFO L290 TraceCheckUtils]: 2: Hoare triple {41#false} assume true; {41#false} is VALID [2022-04-15 15:13:34,879 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {41#false} {41#false} #92#return; {41#false} is VALID [2022-04-15 15:13:34,879 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-15 15:13:34,881 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:13:34,885 INFO L290 TraceCheckUtils]: 0: Hoare triple {40#true} ~cond := #in~cond; {40#true} is VALID [2022-04-15 15:13:34,886 INFO L290 TraceCheckUtils]: 1: Hoare triple {40#true} assume 0 == ~cond;assume false; {41#false} is VALID [2022-04-15 15:13:34,886 INFO L290 TraceCheckUtils]: 2: Hoare triple {41#false} assume true; {41#false} is VALID [2022-04-15 15:13:34,886 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {41#false} {41#false} #94#return; {41#false} is VALID [2022-04-15 15:13:34,886 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-04-15 15:13:34,888 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:13:34,893 INFO L290 TraceCheckUtils]: 0: Hoare triple {40#true} ~cond := #in~cond; {40#true} is VALID [2022-04-15 15:13:34,894 INFO L290 TraceCheckUtils]: 1: Hoare triple {40#true} assume 0 == ~cond;assume false; {41#false} is VALID [2022-04-15 15:13:34,894 INFO L290 TraceCheckUtils]: 2: Hoare triple {41#false} assume true; {41#false} is VALID [2022-04-15 15:13:34,894 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {41#false} {41#false} #96#return; {41#false} is VALID [2022-04-15 15:13:34,895 INFO L272 TraceCheckUtils]: 0: Hoare triple {40#true} call ULTIMATE.init(); {61#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 15:13:34,896 INFO L290 TraceCheckUtils]: 1: Hoare triple {61#(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(13, 2);call #Ultimate.allocInit(12, 3); {40#true} is VALID [2022-04-15 15:13:34,896 INFO L290 TraceCheckUtils]: 2: Hoare triple {40#true} assume true; {40#true} is VALID [2022-04-15 15:13:34,896 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {40#true} {40#true} #106#return; {40#true} is VALID [2022-04-15 15:13:34,896 INFO L272 TraceCheckUtils]: 4: Hoare triple {40#true} call #t~ret6 := main(); {40#true} is VALID [2022-04-15 15:13:34,896 INFO L290 TraceCheckUtils]: 5: Hoare triple {40#true} havoc ~A~0;havoc ~R~0;havoc ~u~0;havoc ~v~0;havoc ~r~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4; {40#true} is VALID [2022-04-15 15:13:34,896 INFO L272 TraceCheckUtils]: 6: Hoare triple {40#true} call assume_abort_if_not((if ~A~0 >= 0 && ~A~0 <= 5 then 1 else 0)); {40#true} is VALID [2022-04-15 15:13:34,897 INFO L290 TraceCheckUtils]: 7: Hoare triple {40#true} ~cond := #in~cond; {40#true} is VALID [2022-04-15 15:13:34,899 INFO L290 TraceCheckUtils]: 8: Hoare triple {40#true} assume 0 == ~cond;assume false; {41#false} is VALID [2022-04-15 15:13:34,899 INFO L290 TraceCheckUtils]: 9: Hoare triple {41#false} assume true; {41#false} is VALID [2022-04-15 15:13:34,899 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {41#false} {40#true} #90#return; {41#false} is VALID [2022-04-15 15:13:34,899 INFO L290 TraceCheckUtils]: 11: Hoare triple {41#false} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~R~0 := #t~nondet5;havoc #t~nondet5; {41#false} is VALID [2022-04-15 15:13:34,899 INFO L272 TraceCheckUtils]: 12: Hoare triple {41#false} call assume_abort_if_not((if ~R~0 >= 0 && ~R~0 <= 5 then 1 else 0)); {40#true} is VALID [2022-04-15 15:13:34,899 INFO L290 TraceCheckUtils]: 13: Hoare triple {40#true} ~cond := #in~cond; {40#true} is VALID [2022-04-15 15:13:34,901 INFO L290 TraceCheckUtils]: 14: Hoare triple {40#true} assume 0 == ~cond;assume false; {41#false} is VALID [2022-04-15 15:13:34,901 INFO L290 TraceCheckUtils]: 15: Hoare triple {41#false} assume true; {41#false} is VALID [2022-04-15 15:13:34,901 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {41#false} {41#false} #92#return; {41#false} is VALID [2022-04-15 15:13:34,901 INFO L272 TraceCheckUtils]: 17: Hoare triple {41#false} call assume_abort_if_not((if (~R~0 - 1) * (~R~0 - 1) < ~A~0 then 1 else 0)); {40#true} is VALID [2022-04-15 15:13:34,901 INFO L290 TraceCheckUtils]: 18: Hoare triple {40#true} ~cond := #in~cond; {40#true} is VALID [2022-04-15 15:13:34,902 INFO L290 TraceCheckUtils]: 19: Hoare triple {40#true} assume 0 == ~cond;assume false; {41#false} is VALID [2022-04-15 15:13:34,902 INFO L290 TraceCheckUtils]: 20: Hoare triple {41#false} assume true; {41#false} is VALID [2022-04-15 15:13:34,902 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {41#false} {41#false} #94#return; {41#false} is VALID [2022-04-15 15:13:34,903 INFO L272 TraceCheckUtils]: 22: Hoare triple {41#false} call assume_abort_if_not((if 1 == (if ~A~0 < 0 && 0 != ~A~0 % 2 then ~A~0 % 2 - 2 else ~A~0 % 2) then 1 else 0)); {40#true} is VALID [2022-04-15 15:13:34,903 INFO L290 TraceCheckUtils]: 23: Hoare triple {40#true} ~cond := #in~cond; {40#true} is VALID [2022-04-15 15:13:34,904 INFO L290 TraceCheckUtils]: 24: Hoare triple {40#true} assume 0 == ~cond;assume false; {41#false} is VALID [2022-04-15 15:13:34,904 INFO L290 TraceCheckUtils]: 25: Hoare triple {41#false} assume true; {41#false} is VALID [2022-04-15 15:13:34,904 INFO L284 TraceCheckUtils]: 26: Hoare quadruple {41#false} {41#false} #96#return; {41#false} is VALID [2022-04-15 15:13:34,904 INFO L290 TraceCheckUtils]: 27: Hoare triple {41#false} ~u~0 := 1 + 2 * ~R~0;~v~0 := 1;~r~0 := ~R~0 * ~R~0 - ~A~0; {41#false} is VALID [2022-04-15 15:13:34,904 INFO L290 TraceCheckUtils]: 28: Hoare triple {41#false} assume !true; {41#false} is VALID [2022-04-15 15:13:34,904 INFO L272 TraceCheckUtils]: 29: Hoare triple {41#false} call __VERIFIER_assert((if 4 * ~A~0 == ~u~0 * ~u~0 - ~v~0 * ~v~0 - 2 * ~u~0 + 2 * ~v~0 then 1 else 0)); {41#false} is VALID [2022-04-15 15:13:34,905 INFO L290 TraceCheckUtils]: 30: Hoare triple {41#false} ~cond := #in~cond; {41#false} is VALID [2022-04-15 15:13:34,905 INFO L290 TraceCheckUtils]: 31: Hoare triple {41#false} assume 0 == ~cond; {41#false} is VALID [2022-04-15 15:13:34,905 INFO L290 TraceCheckUtils]: 32: Hoare triple {41#false} assume !false; {41#false} is VALID [2022-04-15 15:13:34,905 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-15 15:13:34,906 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:13:34,906 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [734035859] [2022-04-15 15:13:34,906 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [734035859] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:13:34,907 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:13:34,907 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 15:13:34,908 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:13:34,909 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [631257524] [2022-04-15 15:13:34,909 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [631257524] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:13:34,909 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:13:34,909 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 15:13:34,909 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [330942113] [2022-04-15 15:13:34,910 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:13:34,913 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-04-15 15:13:34,914 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:13:34,916 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 15:13:34,948 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 24 edges. 24 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:13:34,948 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-15 15:13:34,948 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:13:34,963 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-15 15:13:34,964 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 15:13:34,965 INFO L87 Difference]: Start difference. First operand has 37 states, 21 states have (on average 1.5714285714285714) internal successors, (33), 22 states have internal predecessors, (33), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 15:13:35,123 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:13:35,123 INFO L93 Difference]: Finished difference Result 67 states and 106 transitions. [2022-04-15 15:13:35,123 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-15 15:13:35,124 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-04-15 15:13:35,124 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:13:35,125 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 15:13:35,135 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 106 transitions. [2022-04-15 15:13:35,135 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 15:13:35,143 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 106 transitions. [2022-04-15 15:13:35,143 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 106 transitions. [2022-04-15 15:13:35,252 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 106 edges. 106 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:13:35,266 INFO L225 Difference]: With dead ends: 67 [2022-04-15 15:13:35,267 INFO L226 Difference]: Without dead ends: 32 [2022-04-15 15:13:35,269 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 15 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 15:13:35,274 INFO L913 BasicCegarLoop]: 37 mSDtfsCounter, 22 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 15:13:35,276 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 40 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 15:13:35,286 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-15 15:13:35,306 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-04-15 15:13:35,306 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:13:35,308 INFO L82 GeneralOperation]: Start isEquivalent. First operand 32 states. Second operand has 32 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:13:35,308 INFO L74 IsIncluded]: Start isIncluded. First operand 32 states. Second operand has 32 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:13:35,309 INFO L87 Difference]: Start difference. First operand 32 states. Second operand has 32 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:13:35,320 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:13:35,320 INFO L93 Difference]: Finished difference Result 32 states and 40 transitions. [2022-04-15 15:13:35,320 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 40 transitions. [2022-04-15 15:13:35,321 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:13:35,321 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:13:35,322 INFO L74 IsIncluded]: Start isIncluded. First operand has 32 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 32 states. [2022-04-15 15:13:35,323 INFO L87 Difference]: Start difference. First operand has 32 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 32 states. [2022-04-15 15:13:35,329 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:13:35,329 INFO L93 Difference]: Finished difference Result 32 states and 40 transitions. [2022-04-15 15:13:35,330 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 40 transitions. [2022-04-15 15:13:35,330 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:13:35,330 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:13:35,330 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:13:35,331 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:13:35,332 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-15 15:13:35,335 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 40 transitions. [2022-04-15 15:13:35,336 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 40 transitions. Word has length 33 [2022-04-15 15:13:35,336 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:13:35,337 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 40 transitions. [2022-04-15 15:13:35,337 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 15:13:35,337 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 32 states and 40 transitions. [2022-04-15 15:13:35,374 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 15:13:35,374 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 40 transitions. [2022-04-15 15:13:35,376 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-04-15 15:13:35,376 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:13:35,376 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:13:35,377 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-15 15:13:35,377 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:13:35,378 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:13:35,378 INFO L85 PathProgramCache]: Analyzing trace with hash 657160210, now seen corresponding path program 1 times [2022-04-15 15:13:35,378 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:13:35,379 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1994288882] [2022-04-15 15:13:35,379 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:13:35,379 INFO L85 PathProgramCache]: Analyzing trace with hash 657160210, now seen corresponding path program 2 times [2022-04-15 15:13:35,380 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:13:35,380 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [810757369] [2022-04-15 15:13:35,380 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:13:35,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:13:35,405 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:13:35,405 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1919325937] [2022-04-15 15:13:35,405 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 15:13:35,406 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:13:35,406 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:13:35,416 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 15:13:35,417 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 15:13:35,480 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-15 15:13:35,480 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 15:13:35,490 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-15 15:13:35,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:13:35,507 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 15:13:37,737 INFO L272 TraceCheckUtils]: 0: Hoare triple {326#true} call ULTIMATE.init(); {326#true} is VALID [2022-04-15 15:13:37,737 INFO L290 TraceCheckUtils]: 1: Hoare triple {326#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {326#true} is VALID [2022-04-15 15:13:37,737 INFO L290 TraceCheckUtils]: 2: Hoare triple {326#true} assume true; {326#true} is VALID [2022-04-15 15:13:37,737 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {326#true} {326#true} #106#return; {326#true} is VALID [2022-04-15 15:13:37,738 INFO L272 TraceCheckUtils]: 4: Hoare triple {326#true} call #t~ret6 := main(); {326#true} is VALID [2022-04-15 15:13:37,738 INFO L290 TraceCheckUtils]: 5: Hoare triple {326#true} havoc ~A~0;havoc ~R~0;havoc ~u~0;havoc ~v~0;havoc ~r~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4; {326#true} is VALID [2022-04-15 15:13:37,738 INFO L272 TraceCheckUtils]: 6: Hoare triple {326#true} call assume_abort_if_not((if ~A~0 >= 0 && ~A~0 <= 5 then 1 else 0)); {326#true} is VALID [2022-04-15 15:13:37,738 INFO L290 TraceCheckUtils]: 7: Hoare triple {326#true} ~cond := #in~cond; {326#true} is VALID [2022-04-15 15:13:37,738 INFO L290 TraceCheckUtils]: 8: Hoare triple {326#true} assume !(0 == ~cond); {326#true} is VALID [2022-04-15 15:13:37,738 INFO L290 TraceCheckUtils]: 9: Hoare triple {326#true} assume true; {326#true} is VALID [2022-04-15 15:13:37,739 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {326#true} {326#true} #90#return; {326#true} is VALID [2022-04-15 15:13:37,739 INFO L290 TraceCheckUtils]: 11: Hoare triple {326#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~R~0 := #t~nondet5;havoc #t~nondet5; {326#true} is VALID [2022-04-15 15:13:37,739 INFO L272 TraceCheckUtils]: 12: Hoare triple {326#true} call assume_abort_if_not((if ~R~0 >= 0 && ~R~0 <= 5 then 1 else 0)); {326#true} is VALID [2022-04-15 15:13:37,739 INFO L290 TraceCheckUtils]: 13: Hoare triple {326#true} ~cond := #in~cond; {326#true} is VALID [2022-04-15 15:13:37,739 INFO L290 TraceCheckUtils]: 14: Hoare triple {326#true} assume !(0 == ~cond); {326#true} is VALID [2022-04-15 15:13:37,739 INFO L290 TraceCheckUtils]: 15: Hoare triple {326#true} assume true; {326#true} is VALID [2022-04-15 15:13:37,740 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {326#true} {326#true} #92#return; {326#true} is VALID [2022-04-15 15:13:37,740 INFO L272 TraceCheckUtils]: 17: Hoare triple {326#true} call assume_abort_if_not((if (~R~0 - 1) * (~R~0 - 1) < ~A~0 then 1 else 0)); {326#true} is VALID [2022-04-15 15:13:37,740 INFO L290 TraceCheckUtils]: 18: Hoare triple {326#true} ~cond := #in~cond; {326#true} is VALID [2022-04-15 15:13:37,740 INFO L290 TraceCheckUtils]: 19: Hoare triple {326#true} assume !(0 == ~cond); {326#true} is VALID [2022-04-15 15:13:37,740 INFO L290 TraceCheckUtils]: 20: Hoare triple {326#true} assume true; {326#true} is VALID [2022-04-15 15:13:37,740 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {326#true} {326#true} #94#return; {326#true} is VALID [2022-04-15 15:13:37,741 INFO L272 TraceCheckUtils]: 22: Hoare triple {326#true} call assume_abort_if_not((if 1 == (if ~A~0 < 0 && 0 != ~A~0 % 2 then ~A~0 % 2 - 2 else ~A~0 % 2) then 1 else 0)); {326#true} is VALID [2022-04-15 15:13:37,741 INFO L290 TraceCheckUtils]: 23: Hoare triple {326#true} ~cond := #in~cond; {326#true} is VALID [2022-04-15 15:13:37,741 INFO L290 TraceCheckUtils]: 24: Hoare triple {326#true} assume !(0 == ~cond); {326#true} is VALID [2022-04-15 15:13:37,741 INFO L290 TraceCheckUtils]: 25: Hoare triple {326#true} assume true; {326#true} is VALID [2022-04-15 15:13:37,741 INFO L284 TraceCheckUtils]: 26: Hoare quadruple {326#true} {326#true} #96#return; {326#true} is VALID [2022-04-15 15:13:38,045 INFO L290 TraceCheckUtils]: 27: Hoare triple {326#true} ~u~0 := 1 + 2 * ~R~0;~v~0 := 1;~r~0 := ~R~0 * ~R~0 - ~A~0; {412#(and (= (+ (* (- 1) main_~A~0) (* (div (+ (* (- 1) main_~u~0) 1) (- 2)) (div (+ (* (- 1) main_~u~0) 1) (- 2)))) main_~r~0) (= (mod (+ main_~u~0 1) 2) 0) (= main_~v~0 1))} is VALID [2022-04-15 15:13:38,046 INFO L290 TraceCheckUtils]: 28: Hoare triple {412#(and (= (+ (* (- 1) main_~A~0) (* (div (+ (* (- 1) main_~u~0) 1) (- 2)) (div (+ (* (- 1) main_~u~0) 1) (- 2)))) main_~r~0) (= (mod (+ main_~u~0 1) 2) 0) (= main_~v~0 1))} assume !false; {412#(and (= (+ (* (- 1) main_~A~0) (* (div (+ (* (- 1) main_~u~0) 1) (- 2)) (div (+ (* (- 1) main_~u~0) 1) (- 2)))) main_~r~0) (= (mod (+ main_~u~0 1) 2) 0) (= main_~v~0 1))} is VALID [2022-04-15 15:13:40,048 WARN L272 TraceCheckUtils]: 29: Hoare triple {412#(and (= (+ (* (- 1) main_~A~0) (* (div (+ (* (- 1) main_~u~0) 1) (- 2)) (div (+ (* (- 1) main_~u~0) 1) (- 2)))) main_~r~0) (= (mod (+ main_~u~0 1) 2) 0) (= main_~v~0 1))} call __VERIFIER_assert((if 4 * (~A~0 + ~r~0) == ~u~0 * ~u~0 - ~v~0 * ~v~0 - 2 * ~u~0 + 2 * ~v~0 then 1 else 0)); {419#(<= 1 |__VERIFIER_assert_#in~cond|)} is UNKNOWN [2022-04-15 15:13:40,049 INFO L290 TraceCheckUtils]: 30: Hoare triple {419#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {423#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 15:13:40,050 INFO L290 TraceCheckUtils]: 31: Hoare triple {423#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {327#false} is VALID [2022-04-15 15:13:40,050 INFO L290 TraceCheckUtils]: 32: Hoare triple {327#false} assume !false; {327#false} is VALID [2022-04-15 15:13:40,050 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-15 15:13:40,050 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 15:13:40,051 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:13:40,051 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [810757369] [2022-04-15 15:13:40,051 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 15:13:40,051 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1919325937] [2022-04-15 15:13:40,051 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1919325937] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:13:40,051 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:13:40,051 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:13:40,052 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:13:40,052 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1994288882] [2022-04-15 15:13:40,052 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1994288882] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:13:40,053 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:13:40,053 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 15:13:40,053 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1876948033] [2022-04-15 15:13:40,053 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:13:40,053 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 33 [2022-04-15 15:13:40,054 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:13:40,054 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-04-15 15:13:42,500 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 24 edges. 23 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-15 15:13:42,500 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 15:13:42,500 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:13:42,501 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 15:13:42,501 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 15:13:42,501 INFO L87 Difference]: Start difference. First operand 32 states and 40 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-04-15 15:13:53,506 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.72s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-15 15:13:55,418 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.34s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-15 15:13:58,741 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 15:13:58,772 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:13:58,773 INFO L93 Difference]: Finished difference Result 48 states and 61 transitions. [2022-04-15 15:13:58,773 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 15:13:58,773 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 33 [2022-04-15 15:13:58,773 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:13:58,773 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-04-15 15:13:58,775 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 61 transitions. [2022-04-15 15:13:58,775 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-04-15 15:13:58,777 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 61 transitions. [2022-04-15 15:13:58,777 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 61 transitions. [2022-04-15 15:14:02,551 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 61 edges. 60 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-15 15:14:02,553 INFO L225 Difference]: With dead ends: 48 [2022-04-15 15:14:02,553 INFO L226 Difference]: Without dead ends: 46 [2022-04-15 15:14:02,553 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 29 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 15:14:02,554 INFO L913 BasicCegarLoop]: 32 mSDtfsCounter, 11 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 2 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.0s IncrementalHoareTripleChecker+Time [2022-04-15 15:14:02,554 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 111 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 56 Invalid, 1 Unknown, 0 Unchecked, 9.0s Time] [2022-04-15 15:14:02,555 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2022-04-15 15:14:02,564 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 45. [2022-04-15 15:14:02,564 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:14:02,565 INFO L82 GeneralOperation]: Start isEquivalent. First operand 46 states. Second operand has 45 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 28 states have internal predecessors, (34), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 15:14:02,565 INFO L74 IsIncluded]: Start isIncluded. First operand 46 states. Second operand has 45 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 28 states have internal predecessors, (34), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 15:14:02,565 INFO L87 Difference]: Start difference. First operand 46 states. Second operand has 45 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 28 states have internal predecessors, (34), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 15:14:02,568 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:14:02,568 INFO L93 Difference]: Finished difference Result 46 states and 59 transitions. [2022-04-15 15:14:02,568 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 59 transitions. [2022-04-15 15:14:02,568 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:14:02,568 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:14:02,569 INFO L74 IsIncluded]: Start isIncluded. First operand has 45 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 28 states have internal predecessors, (34), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 46 states. [2022-04-15 15:14:02,569 INFO L87 Difference]: Start difference. First operand has 45 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 28 states have internal predecessors, (34), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 46 states. [2022-04-15 15:14:02,571 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:14:02,571 INFO L93 Difference]: Finished difference Result 46 states and 59 transitions. [2022-04-15 15:14:02,571 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 59 transitions. [2022-04-15 15:14:02,572 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:14:02,572 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:14:02,572 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:14:02,572 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:14:02,572 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 27 states have (on average 1.2592592592592593) internal successors, (34), 28 states have internal predecessors, (34), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 15:14:02,574 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 58 transitions. [2022-04-15 15:14:02,574 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 58 transitions. Word has length 33 [2022-04-15 15:14:02,574 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:14:02,574 INFO L478 AbstractCegarLoop]: Abstraction has 45 states and 58 transitions. [2022-04-15 15:14:02,575 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-04-15 15:14:02,575 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 45 states and 58 transitions. [2022-04-15 15:14:06,459 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 58 edges. 57 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-15 15:14:06,459 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 58 transitions. [2022-04-15 15:14:06,460 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-04-15 15:14:06,460 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 15:14:06,460 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 15:14:06,466 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 15:14:06,664 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 15:14:06,665 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 15:14:06,665 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 15:14:06,666 INFO L85 PathProgramCache]: Analyzing trace with hash 936002262, now seen corresponding path program 1 times [2022-04-15 15:14:06,666 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 15:14:06,666 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1593803297] [2022-04-15 15:14:06,666 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 15:14:06,666 INFO L85 PathProgramCache]: Analyzing trace with hash 936002262, now seen corresponding path program 2 times [2022-04-15 15:14:06,666 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 15:14:06,667 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1863881274] [2022-04-15 15:14:06,667 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 15:14:06,667 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 15:14:06,686 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 15:14:06,686 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1070715512] [2022-04-15 15:14:06,686 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 15:14:06,686 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 15:14:06,687 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 15:14:06,704 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 15:14:06,705 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 15:14:06,742 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 15:14:06,742 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 15:14:06,743 INFO L263 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 10 conjunts are in the unsatisfiable core [2022-04-15 15:14:06,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 15:14:06,752 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 15:14:06,928 INFO L272 TraceCheckUtils]: 0: Hoare triple {709#true} call ULTIMATE.init(); {709#true} is VALID [2022-04-15 15:14:06,928 INFO L290 TraceCheckUtils]: 1: Hoare triple {709#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {709#true} is VALID [2022-04-15 15:14:06,928 INFO L290 TraceCheckUtils]: 2: Hoare triple {709#true} assume true; {709#true} is VALID [2022-04-15 15:14:06,929 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {709#true} {709#true} #106#return; {709#true} is VALID [2022-04-15 15:14:06,929 INFO L272 TraceCheckUtils]: 4: Hoare triple {709#true} call #t~ret6 := main(); {709#true} is VALID [2022-04-15 15:14:06,929 INFO L290 TraceCheckUtils]: 5: Hoare triple {709#true} havoc ~A~0;havoc ~R~0;havoc ~u~0;havoc ~v~0;havoc ~r~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4; {709#true} is VALID [2022-04-15 15:14:06,929 INFO L272 TraceCheckUtils]: 6: Hoare triple {709#true} call assume_abort_if_not((if ~A~0 >= 0 && ~A~0 <= 5 then 1 else 0)); {709#true} is VALID [2022-04-15 15:14:06,929 INFO L290 TraceCheckUtils]: 7: Hoare triple {709#true} ~cond := #in~cond; {709#true} is VALID [2022-04-15 15:14:06,929 INFO L290 TraceCheckUtils]: 8: Hoare triple {709#true} assume !(0 == ~cond); {709#true} is VALID [2022-04-15 15:14:06,929 INFO L290 TraceCheckUtils]: 9: Hoare triple {709#true} assume true; {709#true} is VALID [2022-04-15 15:14:06,929 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {709#true} {709#true} #90#return; {709#true} is VALID [2022-04-15 15:14:06,930 INFO L290 TraceCheckUtils]: 11: Hoare triple {709#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~R~0 := #t~nondet5;havoc #t~nondet5; {709#true} is VALID [2022-04-15 15:14:06,930 INFO L272 TraceCheckUtils]: 12: Hoare triple {709#true} call assume_abort_if_not((if ~R~0 >= 0 && ~R~0 <= 5 then 1 else 0)); {709#true} is VALID [2022-04-15 15:14:06,930 INFO L290 TraceCheckUtils]: 13: Hoare triple {709#true} ~cond := #in~cond; {709#true} is VALID [2022-04-15 15:14:06,930 INFO L290 TraceCheckUtils]: 14: Hoare triple {709#true} assume !(0 == ~cond); {709#true} is VALID [2022-04-15 15:14:06,930 INFO L290 TraceCheckUtils]: 15: Hoare triple {709#true} assume true; {709#true} is VALID [2022-04-15 15:14:06,932 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {709#true} {709#true} #92#return; {709#true} is VALID [2022-04-15 15:14:06,932 INFO L272 TraceCheckUtils]: 17: Hoare triple {709#true} call assume_abort_if_not((if (~R~0 - 1) * (~R~0 - 1) < ~A~0 then 1 else 0)); {709#true} is VALID [2022-04-15 15:14:06,933 INFO L290 TraceCheckUtils]: 18: Hoare triple {709#true} ~cond := #in~cond; {709#true} is VALID [2022-04-15 15:14:06,933 INFO L290 TraceCheckUtils]: 19: Hoare triple {709#true} assume !(0 == ~cond); {709#true} is VALID [2022-04-15 15:14:06,933 INFO L290 TraceCheckUtils]: 20: Hoare triple {709#true} assume true; {709#true} is VALID [2022-04-15 15:14:06,933 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {709#true} {709#true} #94#return; {709#true} is VALID [2022-04-15 15:14:06,933 INFO L272 TraceCheckUtils]: 22: Hoare triple {709#true} call assume_abort_if_not((if 1 == (if ~A~0 < 0 && 0 != ~A~0 % 2 then ~A~0 % 2 - 2 else ~A~0 % 2) then 1 else 0)); {709#true} is VALID [2022-04-15 15:14:06,933 INFO L290 TraceCheckUtils]: 23: Hoare triple {709#true} ~cond := #in~cond; {709#true} is VALID [2022-04-15 15:14:06,933 INFO L290 TraceCheckUtils]: 24: Hoare triple {709#true} assume !(0 == ~cond); {709#true} is VALID [2022-04-15 15:14:06,933 INFO L290 TraceCheckUtils]: 25: Hoare triple {709#true} assume true; {709#true} is VALID [2022-04-15 15:14:06,934 INFO L284 TraceCheckUtils]: 26: Hoare quadruple {709#true} {709#true} #96#return; {709#true} is VALID [2022-04-15 15:14:06,934 INFO L290 TraceCheckUtils]: 27: Hoare triple {709#true} ~u~0 := 1 + 2 * ~R~0;~v~0 := 1;~r~0 := ~R~0 * ~R~0 - ~A~0; {709#true} is VALID [2022-04-15 15:14:06,934 INFO L290 TraceCheckUtils]: 28: Hoare triple {709#true} assume !false; {709#true} is VALID [2022-04-15 15:14:06,934 INFO L272 TraceCheckUtils]: 29: Hoare triple {709#true} call __VERIFIER_assert((if 4 * (~A~0 + ~r~0) == ~u~0 * ~u~0 - ~v~0 * ~v~0 - 2 * ~u~0 + 2 * ~v~0 then 1 else 0)); {709#true} is VALID [2022-04-15 15:14:06,935 INFO L290 TraceCheckUtils]: 30: Hoare triple {709#true} ~cond := #in~cond; {804#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-15 15:14:06,936 INFO L290 TraceCheckUtils]: 31: Hoare triple {804#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {808#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 15:14:06,936 INFO L290 TraceCheckUtils]: 32: Hoare triple {808#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {808#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 15:14:06,938 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {808#(not (= |__VERIFIER_assert_#in~cond| 0))} {709#true} #98#return; {815#(= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4) (* main_~r~0 4)))} is VALID [2022-04-15 15:14:06,939 INFO L290 TraceCheckUtils]: 34: Hoare triple {815#(= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4) (* main_~r~0 4)))} assume !(0 != ~r~0); {819#(= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4)))} is VALID [2022-04-15 15:14:06,947 INFO L272 TraceCheckUtils]: 35: Hoare triple {819#(= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4)))} call __VERIFIER_assert((if 4 * ~A~0 == ~u~0 * ~u~0 - ~v~0 * ~v~0 - 2 * ~u~0 + 2 * ~v~0 then 1 else 0)); {823#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 15:14:06,948 INFO L290 TraceCheckUtils]: 36: Hoare triple {823#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {827#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 15:14:06,948 INFO L290 TraceCheckUtils]: 37: Hoare triple {827#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {710#false} is VALID [2022-04-15 15:14:06,948 INFO L290 TraceCheckUtils]: 38: Hoare triple {710#false} assume !false; {710#false} is VALID [2022-04-15 15:14:06,949 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-15 15:14:06,949 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-15 15:14:07,353 INFO L290 TraceCheckUtils]: 38: Hoare triple {710#false} assume !false; {710#false} is VALID [2022-04-15 15:14:07,354 INFO L290 TraceCheckUtils]: 37: Hoare triple {827#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {710#false} is VALID [2022-04-15 15:14:07,354 INFO L290 TraceCheckUtils]: 36: Hoare triple {823#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {827#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 15:14:07,355 INFO L272 TraceCheckUtils]: 35: Hoare triple {819#(= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4)))} call __VERIFIER_assert((if 4 * ~A~0 == ~u~0 * ~u~0 - ~v~0 * ~v~0 - 2 * ~u~0 + 2 * ~v~0 then 1 else 0)); {823#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 15:14:07,355 INFO L290 TraceCheckUtils]: 34: Hoare triple {846#(or (not (= main_~r~0 0)) (= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4))))} assume !(0 != ~r~0); {819#(= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4)))} is VALID [2022-04-15 15:14:07,356 INFO L284 TraceCheckUtils]: 33: Hoare quadruple {808#(not (= |__VERIFIER_assert_#in~cond| 0))} {709#true} #98#return; {846#(or (not (= main_~r~0 0)) (= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4))))} is VALID [2022-04-15 15:14:07,357 INFO L290 TraceCheckUtils]: 32: Hoare triple {808#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {808#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 15:14:07,357 INFO L290 TraceCheckUtils]: 31: Hoare triple {859#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {808#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 15:14:07,358 INFO L290 TraceCheckUtils]: 30: Hoare triple {709#true} ~cond := #in~cond; {859#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 15:14:07,358 INFO L272 TraceCheckUtils]: 29: Hoare triple {709#true} call __VERIFIER_assert((if 4 * (~A~0 + ~r~0) == ~u~0 * ~u~0 - ~v~0 * ~v~0 - 2 * ~u~0 + 2 * ~v~0 then 1 else 0)); {709#true} is VALID [2022-04-15 15:14:07,358 INFO L290 TraceCheckUtils]: 28: Hoare triple {709#true} assume !false; {709#true} is VALID [2022-04-15 15:14:07,358 INFO L290 TraceCheckUtils]: 27: Hoare triple {709#true} ~u~0 := 1 + 2 * ~R~0;~v~0 := 1;~r~0 := ~R~0 * ~R~0 - ~A~0; {709#true} is VALID [2022-04-15 15:14:07,359 INFO L284 TraceCheckUtils]: 26: Hoare quadruple {709#true} {709#true} #96#return; {709#true} is VALID [2022-04-15 15:14:07,359 INFO L290 TraceCheckUtils]: 25: Hoare triple {709#true} assume true; {709#true} is VALID [2022-04-15 15:14:07,359 INFO L290 TraceCheckUtils]: 24: Hoare triple {709#true} assume !(0 == ~cond); {709#true} is VALID [2022-04-15 15:14:07,359 INFO L290 TraceCheckUtils]: 23: Hoare triple {709#true} ~cond := #in~cond; {709#true} is VALID [2022-04-15 15:14:07,359 INFO L272 TraceCheckUtils]: 22: Hoare triple {709#true} call assume_abort_if_not((if 1 == (if ~A~0 < 0 && 0 != ~A~0 % 2 then ~A~0 % 2 - 2 else ~A~0 % 2) then 1 else 0)); {709#true} is VALID [2022-04-15 15:14:07,359 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {709#true} {709#true} #94#return; {709#true} is VALID [2022-04-15 15:14:07,360 INFO L290 TraceCheckUtils]: 20: Hoare triple {709#true} assume true; {709#true} is VALID [2022-04-15 15:14:07,360 INFO L290 TraceCheckUtils]: 19: Hoare triple {709#true} assume !(0 == ~cond); {709#true} is VALID [2022-04-15 15:14:07,360 INFO L290 TraceCheckUtils]: 18: Hoare triple {709#true} ~cond := #in~cond; {709#true} is VALID [2022-04-15 15:14:07,360 INFO L272 TraceCheckUtils]: 17: Hoare triple {709#true} call assume_abort_if_not((if (~R~0 - 1) * (~R~0 - 1) < ~A~0 then 1 else 0)); {709#true} is VALID [2022-04-15 15:14:07,360 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {709#true} {709#true} #92#return; {709#true} is VALID [2022-04-15 15:14:07,360 INFO L290 TraceCheckUtils]: 15: Hoare triple {709#true} assume true; {709#true} is VALID [2022-04-15 15:14:07,360 INFO L290 TraceCheckUtils]: 14: Hoare triple {709#true} assume !(0 == ~cond); {709#true} is VALID [2022-04-15 15:14:07,361 INFO L290 TraceCheckUtils]: 13: Hoare triple {709#true} ~cond := #in~cond; {709#true} is VALID [2022-04-15 15:14:07,361 INFO L272 TraceCheckUtils]: 12: Hoare triple {709#true} call assume_abort_if_not((if ~R~0 >= 0 && ~R~0 <= 5 then 1 else 0)); {709#true} is VALID [2022-04-15 15:14:07,361 INFO L290 TraceCheckUtils]: 11: Hoare triple {709#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~R~0 := #t~nondet5;havoc #t~nondet5; {709#true} is VALID [2022-04-15 15:14:07,361 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {709#true} {709#true} #90#return; {709#true} is VALID [2022-04-15 15:14:07,361 INFO L290 TraceCheckUtils]: 9: Hoare triple {709#true} assume true; {709#true} is VALID [2022-04-15 15:14:07,361 INFO L290 TraceCheckUtils]: 8: Hoare triple {709#true} assume !(0 == ~cond); {709#true} is VALID [2022-04-15 15:14:07,361 INFO L290 TraceCheckUtils]: 7: Hoare triple {709#true} ~cond := #in~cond; {709#true} is VALID [2022-04-15 15:14:07,362 INFO L272 TraceCheckUtils]: 6: Hoare triple {709#true} call assume_abort_if_not((if ~A~0 >= 0 && ~A~0 <= 5 then 1 else 0)); {709#true} is VALID [2022-04-15 15:14:07,362 INFO L290 TraceCheckUtils]: 5: Hoare triple {709#true} havoc ~A~0;havoc ~R~0;havoc ~u~0;havoc ~v~0;havoc ~r~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~A~0 := #t~nondet4;havoc #t~nondet4; {709#true} is VALID [2022-04-15 15:14:07,362 INFO L272 TraceCheckUtils]: 4: Hoare triple {709#true} call #t~ret6 := main(); {709#true} is VALID [2022-04-15 15:14:07,362 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {709#true} {709#true} #106#return; {709#true} is VALID [2022-04-15 15:14:07,362 INFO L290 TraceCheckUtils]: 2: Hoare triple {709#true} assume true; {709#true} is VALID [2022-04-15 15:14:07,362 INFO L290 TraceCheckUtils]: 1: Hoare triple {709#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {709#true} is VALID [2022-04-15 15:14:07,362 INFO L272 TraceCheckUtils]: 0: Hoare triple {709#true} call ULTIMATE.init(); {709#true} is VALID [2022-04-15 15:14:07,363 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-15 15:14:07,363 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 15:14:07,363 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1863881274] [2022-04-15 15:14:07,363 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 15:14:07,363 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1070715512] [2022-04-15 15:14:07,364 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1070715512] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-15 15:14:07,364 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-15 15:14:07,364 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2022-04-15 15:14:07,364 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 15:14:07,364 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1593803297] [2022-04-15 15:14:07,364 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1593803297] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 15:14:07,364 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 15:14:07,365 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-04-15 15:14:07,365 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [451145436] [2022-04-15 15:14:07,365 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 15:14:07,365 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 1 states have call successors, (6) Word has length 39 [2022-04-15 15:14:07,366 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 15:14:07,366 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 1 states have call successors, (6) [2022-04-15 15:14:07,385 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 30 edges. 30 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 15:14:07,385 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-15 15:14:07,385 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 15:14:07,385 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-15 15:14:07,386 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2022-04-15 15:14:07,386 INFO L87 Difference]: Start difference. First operand 45 states and 58 transitions. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 1 states have call successors, (6) [2022-04-15 15:14:07,774 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:14:07,774 INFO L93 Difference]: Finished difference Result 45 states and 58 transitions. [2022-04-15 15:14:07,774 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-15 15:14:07,774 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 1 states have call successors, (6) Word has length 39 [2022-04-15 15:14:07,774 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 15:14:07,775 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 1 states have call successors, (6) [2022-04-15 15:14:07,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 40 transitions. [2022-04-15 15:14:07,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 1 states have call successors, (6) [2022-04-15 15:14:07,777 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 40 transitions. [2022-04-15 15:14:07,777 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 40 transitions. [2022-04-15 15:14:07,812 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 15:14:07,813 INFO L225 Difference]: With dead ends: 45 [2022-04-15 15:14:07,813 INFO L226 Difference]: Without dead ends: 0 [2022-04-15 15:14:07,813 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 68 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2022-04-15 15:14:07,814 INFO L913 BasicCegarLoop]: 27 mSDtfsCounter, 15 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 75 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 85 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 75 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-15 15:14:07,814 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 126 Invalid, 85 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 75 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-15 15:14:07,815 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-15 15:14:07,815 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-15 15:14:07,815 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 15:14:07,815 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 15:14:07,815 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 15:14:07,815 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 15:14:07,815 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:14:07,815 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-15 15:14:07,816 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-15 15:14:07,816 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:14:07,816 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:14:07,816 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 15:14:07,816 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 15:14:07,816 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 15:14:07,816 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-15 15:14:07,816 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-15 15:14:07,816 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:14:07,816 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 15:14:07,816 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 15:14:07,816 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 15:14:07,816 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 15:14:07,816 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-15 15:14:07,817 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 39 [2022-04-15 15:14:07,817 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 15:14:07,817 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-15 15:14:07,817 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 2 states have call predecessors, (6), 1 states have call successors, (6) [2022-04-15 15:14:07,817 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 0 states and 0 transitions. [2022-04-15 15:14:07,817 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 15:14:07,817 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-15 15:14:07,817 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 15:14:07,819 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-15 15:14:07,837 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-15 15:14:08,034 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 15:14:08,036 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-04-15 15:14:08,295 INFO L882 garLoopResultBuilder]: For program point reach_errorEXIT(line 5) no Hoare annotation was computed. [2022-04-15 15:14:08,295 INFO L882 garLoopResultBuilder]: For program point reach_errorENTRY(line 5) no Hoare annotation was computed. [2022-04-15 15:14:08,295 INFO L882 garLoopResultBuilder]: For program point reach_errorFINAL(line 5) no Hoare annotation was computed. [2022-04-15 15:14:08,295 INFO L885 garLoopResultBuilder]: At program point assume_abort_if_notENTRY(lines 8 10) the Hoare annotation is: true [2022-04-15 15:14:08,295 INFO L885 garLoopResultBuilder]: At program point L9(line 9) the Hoare annotation is: true [2022-04-15 15:14:08,295 INFO L885 garLoopResultBuilder]: At program point L9-2(lines 8 10) the Hoare annotation is: true [2022-04-15 15:14:08,295 INFO L885 garLoopResultBuilder]: At program point assume_abort_if_notEXIT(lines 8 10) the Hoare annotation is: true [2022-04-15 15:14:08,296 INFO L878 garLoopResultBuilder]: At program point L35-2(lines 35 55) the Hoare annotation is: (let ((.cse0 (+ (* main_~v~0 2) (* main_~u~0 main_~u~0))) (.cse1 (* main_~v~0 main_~v~0)) (.cse2 (* main_~u~0 2)) (.cse3 (* main_~A~0 4))) (and (= .cse0 (+ .cse1 .cse2 .cse3 (* main_~r~0 4))) (= .cse0 (+ .cse1 .cse2 .cse3)))) [2022-04-15 15:14:08,296 INFO L885 garLoopResultBuilder]: At program point mainEXIT(lines 19 59) the Hoare annotation is: true [2022-04-15 15:14:08,296 INFO L885 garLoopResultBuilder]: At program point L23(line 23) the Hoare annotation is: true [2022-04-15 15:14:08,296 INFO L885 garLoopResultBuilder]: At program point L23-1(line 23) the Hoare annotation is: true [2022-04-15 15:14:08,296 INFO L878 garLoopResultBuilder]: At program point L48-1(lines 35 55) the Hoare annotation is: (= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4) (* main_~r~0 4))) [2022-04-15 15:14:08,296 INFO L878 garLoopResultBuilder]: At program point L48-2(lines 35 55) the Hoare annotation is: (= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4) (* main_~r~0 4))) [2022-04-15 15:14:08,296 INFO L878 garLoopResultBuilder]: At program point L40-2(lines 40 46) the Hoare annotation is: (= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4) (* main_~r~0 4))) [2022-04-15 15:14:08,296 INFO L878 garLoopResultBuilder]: At program point L36(line 36) the Hoare annotation is: (= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4) (* main_~r~0 4))) [2022-04-15 15:14:08,296 INFO L878 garLoopResultBuilder]: At program point L36-1(lines 35 55) the Hoare annotation is: (= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4) (* main_~r~0 4))) [2022-04-15 15:14:08,296 INFO L885 garLoopResultBuilder]: At program point L28(line 28) the Hoare annotation is: true [2022-04-15 15:14:08,296 INFO L885 garLoopResultBuilder]: At program point L57(line 57) the Hoare annotation is: true [2022-04-15 15:14:08,296 INFO L878 garLoopResultBuilder]: At program point L49(line 49) the Hoare annotation is: (= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4) (* main_~r~0 4))) [2022-04-15 15:14:08,297 INFO L878 garLoopResultBuilder]: At program point L49-1(lines 48 54) the Hoare annotation is: (= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4) (* main_~r~0 4))) [2022-04-15 15:14:08,297 INFO L878 garLoopResultBuilder]: At program point L41(line 41) the Hoare annotation is: (= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4) (* main_~r~0 4))) [2022-04-15 15:14:08,297 INFO L878 garLoopResultBuilder]: At program point L41-1(lines 40 46) the Hoare annotation is: (= (+ (* main_~v~0 2) (* main_~u~0 main_~u~0)) (+ (* main_~v~0 main_~v~0) (* main_~u~0 2) (* main_~A~0 4) (* main_~r~0 4))) [2022-04-15 15:14:08,297 INFO L885 garLoopResultBuilder]: At program point L25(line 25) the Hoare annotation is: true [2022-04-15 15:14:08,297 INFO L885 garLoopResultBuilder]: At program point L25-1(line 25) the Hoare annotation is: true [2022-04-15 15:14:08,297 INFO L885 garLoopResultBuilder]: At program point mainFINAL(lines 19 59) the Hoare annotation is: true [2022-04-15 15:14:08,297 INFO L885 garLoopResultBuilder]: At program point mainENTRY(lines 19 59) the Hoare annotation is: true [2022-04-15 15:14:08,297 INFO L885 garLoopResultBuilder]: At program point L26(line 26) the Hoare annotation is: true [2022-04-15 15:14:08,297 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.initFINAL(line -1) the Hoare annotation is: true [2022-04-15 15:14:08,297 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 15:14:08,297 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.initEXIT(line -1) the Hoare annotation is: true [2022-04-15 15:14:08,297 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startEXIT(line -1) the Hoare annotation is: true [2022-04-15 15:14:08,297 INFO L885 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-04-15 15:14:08,297 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-04-15 15:14:08,298 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startFINAL(line -1) the Hoare annotation is: true [2022-04-15 15:14:08,298 INFO L885 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 11 17) the Hoare annotation is: true [2022-04-15 15:14:08,298 INFO L878 garLoopResultBuilder]: At program point L13(lines 13 14) the Hoare annotation is: (not (<= 1 |__VERIFIER_assert_#in~cond|)) [2022-04-15 15:14:08,298 INFO L878 garLoopResultBuilder]: At program point L12(lines 12 15) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-15 15:14:08,298 INFO L878 garLoopResultBuilder]: At program point L12-2(lines 11 17) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-15 15:14:08,298 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertEXIT(lines 11 17) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-15 15:14:08,298 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 14) the Hoare annotation is: (not (<= 1 |__VERIFIER_assert_#in~cond|)) [2022-04-15 15:14:08,300 INFO L719 BasicCegarLoop]: Path program histogram: [2, 2, 2] [2022-04-15 15:14:08,301 INFO L177 ceAbstractionStarter]: Computing trace abstraction results [2022-04-15 15:14:08,304 WARN L170 areAnnotationChecker]: reach_errorENTRY has no Hoare annotation [2022-04-15 15:14:08,305 WARN L170 areAnnotationChecker]: reach_errorFINAL has no Hoare annotation [2022-04-15 15:14:08,317 INFO L163 areAnnotationChecker]: CFG has 53 edges. 53 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. 0 times interpolants missing. [2022-04-15 15:14:08,324 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 15.04 03:14:08 BoogieIcfgContainer [2022-04-15 15:14:08,324 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-15 15:14:08,325 INFO L158 Benchmark]: Toolchain (without parser) took 34160.66ms. Allocated memory was 176.2MB in the beginning and 219.2MB in the end (delta: 43.0MB). Free memory was 127.7MB in the beginning and 129.7MB in the end (delta: -2.0MB). Peak memory consumption was 42.2MB. Max. memory is 8.0GB. [2022-04-15 15:14:08,325 INFO L158 Benchmark]: CDTParser took 0.11ms. Allocated memory is still 176.2MB. Free memory was 143.7MB in the beginning and 143.5MB in the end (delta: 139.8kB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-15 15:14:08,325 INFO L158 Benchmark]: CACSL2BoogieTranslator took 170.34ms. Allocated memory is still 176.2MB. Free memory was 127.4MB in the beginning and 151.0MB in the end (delta: -23.7MB). Peak memory consumption was 11.9MB. Max. memory is 8.0GB. [2022-04-15 15:14:08,326 INFO L158 Benchmark]: Boogie Preprocessor took 30.26ms. Allocated memory is still 176.2MB. Free memory was 151.0MB in the beginning and 149.5MB in the end (delta: 1.6MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-15 15:14:08,326 INFO L158 Benchmark]: RCFGBuilder took 261.13ms. Allocated memory is still 176.2MB. Free memory was 149.5MB in the beginning and 136.9MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2022-04-15 15:14:08,326 INFO L158 Benchmark]: TraceAbstraction took 33695.70ms. Allocated memory was 176.2MB in the beginning and 219.2MB in the end (delta: 43.0MB). Free memory was 136.4MB in the beginning and 129.7MB in the end (delta: 6.7MB). Peak memory consumption was 51.2MB. Max. memory is 8.0GB. [2022-04-15 15:14:08,328 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 176.2MB. Free memory was 143.7MB in the beginning and 143.5MB in the end (delta: 139.8kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 170.34ms. Allocated memory is still 176.2MB. Free memory was 127.4MB in the beginning and 151.0MB in the end (delta: -23.7MB). Peak memory consumption was 11.9MB. Max. memory is 8.0GB. * Boogie Preprocessor took 30.26ms. Allocated memory is still 176.2MB. Free memory was 151.0MB in the beginning and 149.5MB in the end (delta: 1.6MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 261.13ms. Allocated memory is still 176.2MB. Free memory was 149.5MB in the beginning and 136.9MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * TraceAbstraction took 33695.70ms. Allocated memory was 176.2MB in the beginning and 219.2MB in the end (delta: 43.0MB). Free memory was 136.4MB in the beginning and 129.7MB in the end (delta: 6.7MB). Peak memory consumption was 51.2MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 14]: 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, 40 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 33.6s, OverallIterations: 3, TraceHistogramMax: 4, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 20.8s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.3s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 1 mSolverCounterUnknown, 61 SdHoareTripleChecker+Valid, 9.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 48 mSDsluCounter, 277 SdHoareTripleChecker+Invalid, 9.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 181 mSDsCounter, 21 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 141 IncrementalHoareTripleChecker+Invalid, 163 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 21 mSolverCounterUnsat, 96 mSDtfsCounter, 141 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 128 GetRequests, 112 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=45occurred in iteration=2, InterpolantAutomatonStates: 14, 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, 3 MinimizatonAttempts, 1 StatesRemovedByMinimization, 1 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 37 LocationsWithAnnotation, 121 PreInvPairs, 174 NumberOfFragments, 289 HoareAnnotationTreeSize, 121 FomulaSimplifications, 0 FormulaSimplificationTreeSizeReduction, 0.0s HoareSimplificationTime, 37 FomulaSimplificationsInter, 546 FormulaSimplificationTreeSizeReductionInter, 0.2s 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: 40]: Loop Invariant Derived loop invariant: v * 2 + u * u == v * v + u * 2 + A * 4 + r * 4 - InvariantResult [Line: 35]: Loop Invariant Derived loop invariant: v * 2 + u * u == v * v + u * 2 + A * 4 + r * 4 - ProcedureContractResult [Line: 8]: Procedure Contract for assume_abort_if_not Derived contract for procedure assume_abort_if_not: 1 - ProcedureContractResult [Line: 19]: Procedure Contract for main Derived contract for procedure main: 1 - ProcedureContractResult [Line: 11]: 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 15:14:08,358 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...