/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/sqrt1-ll.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-08 10:56:55,509 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-08 10:56:55,511 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-08 10:56:55,554 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-08 10:56:55,555 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-08 10:56:55,556 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-08 10:56:55,559 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-08 10:56:55,561 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-08 10:56:55,563 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-08 10:56:55,567 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-08 10:56:55,568 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-08 10:56:55,569 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-08 10:56:55,570 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-08 10:56:55,572 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-08 10:56:55,573 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-08 10:56:55,575 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-08 10:56:55,576 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-08 10:56:55,576 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-08 10:56:55,578 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-08 10:56:55,583 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-08 10:56:55,585 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-08 10:56:55,586 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-08 10:56:55,587 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-08 10:56:55,588 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-08 10:56:55,589 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-08 10:56:55,593 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-08 10:56:55,593 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-08 10:56:55,594 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-08 10:56:55,594 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-08 10:56:55,595 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-08 10:56:55,596 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-08 10:56:55,596 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-08 10:56:55,598 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-08 10:56:55,598 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-08 10:56:55,599 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-08 10:56:55,599 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-08 10:56:55,600 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-08 10:56:55,600 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-08 10:56:55,600 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-08 10:56:55,601 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-08 10:56:55,601 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-08 10:56:55,603 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-08 10:56:55,603 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-08 10:56:55,613 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-08 10:56:55,613 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-08 10:56:55,614 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-08 10:56:55,614 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-08 10:56:55,615 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-08 10:56:55,615 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-08 10:56:55,615 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-08 10:56:55,615 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-08 10:56:55,615 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-08 10:56:55,616 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-08 10:56:55,616 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-08 10:56:55,616 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-08 10:56:55,616 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-08 10:56:55,616 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-08 10:56:55,617 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-08 10:56:55,617 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 10:56:55,617 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-08 10:56:55,617 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-08 10:56:55,617 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-08 10:56:55,617 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-08 10:56:55,617 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-08 10:56:55,617 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-08 10:56:55,617 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-08 10:56:55,873 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-08 10:56:55,895 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-08 10:56:55,897 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-08 10:56:55,898 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-08 10:56:55,899 INFO L275 PluginConnector]: CDTParser initialized [2022-04-08 10:56:55,900 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench/sqrt1-ll.c [2022-04-08 10:56:55,962 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2f61ddebc/328fa09fc3fa42f8a9ea8218026916a8/FLAG66e041c13 [2022-04-08 10:56:56,370 INFO L306 CDTParser]: Found 1 translation units. [2022-04-08 10:56:56,370 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench/sqrt1-ll.c [2022-04-08 10:56:56,383 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2f61ddebc/328fa09fc3fa42f8a9ea8218026916a8/FLAG66e041c13 [2022-04-08 10:56:56,769 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2f61ddebc/328fa09fc3fa42f8a9ea8218026916a8 [2022-04-08 10:56:56,771 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-08 10:56:56,772 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-08 10:56:56,775 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-08 10:56:56,776 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-08 10:56:56,779 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-08 10:56:56,780 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 10:56:56" (1/1) ... [2022-04-08 10:56:56,782 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6b23edb1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 10:56:56, skipping insertion in model container [2022-04-08 10:56:56,782 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 10:56:56" (1/1) ... [2022-04-08 10:56:56,792 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-08 10:56:56,803 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-08 10:56:56,987 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/sqrt1-ll.c[520,533] [2022-04-08 10:56:57,026 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 10:56:57,039 INFO L203 MainTranslator]: Completed pre-run [2022-04-08 10:56:57,053 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/sqrt1-ll.c[520,533] [2022-04-08 10:56:57,072 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 10:56:57,085 INFO L208 MainTranslator]: Completed translation [2022-04-08 10:56:57,086 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 10:56:57 WrapperNode [2022-04-08 10:56:57,086 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-08 10:56:57,087 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-08 10:56:57,087 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-08 10:56:57,088 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-08 10:56:57,097 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 10:56:57" (1/1) ... [2022-04-08 10:56:57,097 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 10:56:57" (1/1) ... [2022-04-08 10:56:57,103 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 10:56:57" (1/1) ... [2022-04-08 10:56:57,103 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 10:56:57" (1/1) ... [2022-04-08 10:56:57,118 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 10:56:57" (1/1) ... [2022-04-08 10:56:57,123 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 10:56:57" (1/1) ... [2022-04-08 10:56:57,125 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 10:56:57" (1/1) ... [2022-04-08 10:56:57,130 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-08 10:56:57,131 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-08 10:56:57,131 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-08 10:56:57,132 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-08 10:56:57,132 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 10:56:57" (1/1) ... [2022-04-08 10:56:57,140 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 10:56:57,152 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 10:56:57,166 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-08 10:56:57,192 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-08 10:56:57,213 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-08 10:56:57,213 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-08 10:56:57,213 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-08 10:56:57,214 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-08 10:56:57,214 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-08 10:56:57,214 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-08 10:56:57,214 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-08 10:56:57,214 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-08 10:56:57,214 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-08 10:56:57,215 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-08 10:56:57,215 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-08 10:56:57,215 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-08 10:56:57,215 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-08 10:56:57,215 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-08 10:56:57,216 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-08 10:56:57,217 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-08 10:56:57,217 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-08 10:56:57,217 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-08 10:56:57,217 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-08 10:56:57,217 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-08 10:56:57,276 INFO L234 CfgBuilder]: Building ICFG [2022-04-08 10:56:57,277 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-08 10:56:57,460 INFO L275 CfgBuilder]: Performing block encoding [2022-04-08 10:56:57,466 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-08 10:56:57,466 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-08 10:56:57,476 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 10:56:57 BoogieIcfgContainer [2022-04-08 10:56:57,477 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-08 10:56:57,481 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-08 10:56:57,481 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-08 10:56:57,495 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-08 10:56:57,495 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.04 10:56:56" (1/3) ... [2022-04-08 10:56:57,496 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5031e01 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 10:56:57, skipping insertion in model container [2022-04-08 10:56:57,496 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 10:56:57" (2/3) ... [2022-04-08 10:56:57,496 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5031e01 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 10:56:57, skipping insertion in model container [2022-04-08 10:56:57,497 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 10:56:57" (3/3) ... [2022-04-08 10:56:57,498 INFO L111 eAbstractionObserver]: Analyzing ICFG sqrt1-ll.c [2022-04-08 10:56:57,502 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-08 10:56:57,502 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-08 10:56:57,555 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-08 10:56:57,563 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-08 10:56:57,564 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-08 10:56:57,590 INFO L276 IsEmpty]: Start isEmpty. Operand has 25 states, 12 states have (on average 1.4166666666666667) internal successors, (17), 13 states have internal predecessors, (17), 8 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-08 10:56:57,599 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-04-08 10:56:57,599 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 10:56:57,600 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 10:56:57,600 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 10:56:57,605 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 10:56:57,606 INFO L85 PathProgramCache]: Analyzing trace with hash 515438393, now seen corresponding path program 1 times [2022-04-08 10:56:57,613 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 10:56:57,614 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [35612534] [2022-04-08 10:56:57,624 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 10:56:57,625 INFO L85 PathProgramCache]: Analyzing trace with hash 515438393, now seen corresponding path program 2 times [2022-04-08 10:56:57,627 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 10:56:57,628 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1172386166] [2022-04-08 10:56:57,628 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 10:56:57,629 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 10:56:57,711 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 10:56:57,769 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 10:56:57,780 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 10:56:57,802 INFO L290 TraceCheckUtils]: 0: Hoare triple {33#(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(11, 2);call #Ultimate.allocInit(12, 3); {28#true} is VALID [2022-04-08 10:56:57,802 INFO L290 TraceCheckUtils]: 1: Hoare triple {28#true} assume true; {28#true} is VALID [2022-04-08 10:56:57,802 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {28#true} {28#true} #65#return; {28#true} is VALID [2022-04-08 10:56:57,805 INFO L272 TraceCheckUtils]: 0: Hoare triple {28#true} call ULTIMATE.init(); {33#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 10:56:57,805 INFO L290 TraceCheckUtils]: 1: Hoare triple {33#(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(11, 2);call #Ultimate.allocInit(12, 3); {28#true} is VALID [2022-04-08 10:56:57,806 INFO L290 TraceCheckUtils]: 2: Hoare triple {28#true} assume true; {28#true} is VALID [2022-04-08 10:56:57,806 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {28#true} {28#true} #65#return; {28#true} is VALID [2022-04-08 10:56:57,806 INFO L272 TraceCheckUtils]: 4: Hoare triple {28#true} call #t~ret5 := main(); {28#true} is VALID [2022-04-08 10:56:57,807 INFO L290 TraceCheckUtils]: 5: Hoare triple {28#true} havoc ~n~0;havoc ~a~0;havoc ~s~0;havoc ~t~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~n~0 := #t~nondet4;havoc #t~nondet4;~a~0 := 0;~s~0 := 1;~t~0 := 1; {28#true} is VALID [2022-04-08 10:56:57,808 INFO L290 TraceCheckUtils]: 6: Hoare triple {28#true} assume false; {29#false} is VALID [2022-04-08 10:56:57,808 INFO L272 TraceCheckUtils]: 7: Hoare triple {29#false} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {29#false} is VALID [2022-04-08 10:56:57,808 INFO L290 TraceCheckUtils]: 8: Hoare triple {29#false} ~cond := #in~cond; {29#false} is VALID [2022-04-08 10:56:57,809 INFO L290 TraceCheckUtils]: 9: Hoare triple {29#false} assume 0 == ~cond; {29#false} is VALID [2022-04-08 10:56:57,809 INFO L290 TraceCheckUtils]: 10: Hoare triple {29#false} assume !false; {29#false} is VALID [2022-04-08 10:56:57,810 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 10:56:57,810 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 10:56:57,810 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1172386166] [2022-04-08 10:56:57,811 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1172386166] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 10:56:57,811 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 10:56:57,812 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 10:56:57,815 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 10:56:57,816 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [35612534] [2022-04-08 10:56:57,816 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [35612534] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 10:56:57,816 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 10:56:57,816 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 10:56:57,817 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1105300139] [2022-04-08 10:56:57,817 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 10:56:57,823 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2022-04-08 10:56:57,824 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 10:56:57,827 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 10:56:57,850 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 11 edges. 11 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:56:57,851 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-08 10:56:57,851 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 10:56:57,869 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-08 10:56:57,871 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-08 10:56:57,873 INFO L87 Difference]: Start difference. First operand has 25 states, 12 states have (on average 1.4166666666666667) internal successors, (17), 13 states have internal predecessors, (17), 8 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 10:56:57,999 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:56:57,999 INFO L93 Difference]: Finished difference Result 44 states and 66 transitions. [2022-04-08 10:56:57,999 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-08 10:56:58,000 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2022-04-08 10:56:58,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 10:56:58,001 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 10:56:58,020 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 66 transitions. [2022-04-08 10:56:58,021 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 10:56:58,046 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 66 transitions. [2022-04-08 10:56:58,046 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 66 transitions. [2022-04-08 10:56:58,160 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 66 edges. 66 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:56:58,167 INFO L225 Difference]: With dead ends: 44 [2022-04-08 10:56:58,168 INFO L226 Difference]: Without dead ends: 20 [2022-04-08 10:56:58,170 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-08 10:56:58,173 INFO L913 BasicCegarLoop]: 24 mSDtfsCounter, 11 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 27 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 10:56:58,174 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 27 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 10:56:58,199 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2022-04-08 10:56:58,233 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2022-04-08 10:56:58,234 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 10:56:58,234 INFO L82 GeneralOperation]: Start isEquivalent. First operand 20 states. Second operand has 20 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 10 states have internal predecessors, (11), 8 states have call successors, (8), 3 states have call predecessors, (8), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-08 10:56:58,235 INFO L74 IsIncluded]: Start isIncluded. First operand 20 states. Second operand has 20 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 10 states have internal predecessors, (11), 8 states have call successors, (8), 3 states have call predecessors, (8), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-08 10:56:58,235 INFO L87 Difference]: Start difference. First operand 20 states. Second operand has 20 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 10 states have internal predecessors, (11), 8 states have call successors, (8), 3 states have call predecessors, (8), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-08 10:56:58,240 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:56:58,240 INFO L93 Difference]: Finished difference Result 20 states and 25 transitions. [2022-04-08 10:56:58,240 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 25 transitions. [2022-04-08 10:56:58,241 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 10:56:58,241 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 10:56:58,242 INFO L74 IsIncluded]: Start isIncluded. First operand has 20 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 10 states have internal predecessors, (11), 8 states have call successors, (8), 3 states have call predecessors, (8), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand 20 states. [2022-04-08 10:56:58,242 INFO L87 Difference]: Start difference. First operand has 20 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 10 states have internal predecessors, (11), 8 states have call successors, (8), 3 states have call predecessors, (8), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand 20 states. [2022-04-08 10:56:58,262 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:56:58,263 INFO L93 Difference]: Finished difference Result 20 states and 25 transitions. [2022-04-08 10:56:58,263 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 25 transitions. [2022-04-08 10:56:58,264 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 10:56:58,264 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 10:56:58,264 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 10:56:58,264 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 10:56:58,265 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 10 states have internal predecessors, (11), 8 states have call successors, (8), 3 states have call predecessors, (8), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-08 10:56:58,268 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 25 transitions. [2022-04-08 10:56:58,269 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 25 transitions. Word has length 11 [2022-04-08 10:56:58,269 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 10:56:58,270 INFO L478 AbstractCegarLoop]: Abstraction has 20 states and 25 transitions. [2022-04-08 10:56:58,270 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 10:56:58,270 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 20 states and 25 transitions. [2022-04-08 10:56:58,334 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 25 edges. 25 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:56:58,335 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 25 transitions. [2022-04-08 10:56:58,335 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-04-08 10:56:58,335 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 10:56:58,335 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 10:56:58,336 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-08 10:56:58,336 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 10:56:58,337 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 10:56:58,337 INFO L85 PathProgramCache]: Analyzing trace with hash 517106689, now seen corresponding path program 1 times [2022-04-08 10:56:58,337 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 10:56:58,337 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1072631470] [2022-04-08 10:56:58,338 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 10:56:58,338 INFO L85 PathProgramCache]: Analyzing trace with hash 517106689, now seen corresponding path program 2 times [2022-04-08 10:56:58,338 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 10:56:58,338 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1500324420] [2022-04-08 10:56:58,338 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 10:56:58,338 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 10:56:58,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 10:56:58,473 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 10:56:58,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 10:56:58,504 INFO L290 TraceCheckUtils]: 0: Hoare triple {212#(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(11, 2);call #Ultimate.allocInit(12, 3); {204#true} is VALID [2022-04-08 10:56:58,504 INFO L290 TraceCheckUtils]: 1: Hoare triple {204#true} assume true; {204#true} is VALID [2022-04-08 10:56:58,505 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {204#true} {204#true} #65#return; {204#true} is VALID [2022-04-08 10:56:58,505 INFO L272 TraceCheckUtils]: 0: Hoare triple {204#true} call ULTIMATE.init(); {212#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 10:56:58,506 INFO L290 TraceCheckUtils]: 1: Hoare triple {212#(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(11, 2);call #Ultimate.allocInit(12, 3); {204#true} is VALID [2022-04-08 10:56:58,506 INFO L290 TraceCheckUtils]: 2: Hoare triple {204#true} assume true; {204#true} is VALID [2022-04-08 10:56:58,506 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {204#true} {204#true} #65#return; {204#true} is VALID [2022-04-08 10:56:58,506 INFO L272 TraceCheckUtils]: 4: Hoare triple {204#true} call #t~ret5 := main(); {204#true} is VALID [2022-04-08 10:56:58,513 INFO L290 TraceCheckUtils]: 5: Hoare triple {204#true} havoc ~n~0;havoc ~a~0;havoc ~s~0;havoc ~t~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~n~0 := #t~nondet4;havoc #t~nondet4;~a~0 := 0;~s~0 := 1;~t~0 := 1; {209#(and (= (* main_~a~0 2) 0) (= main_~t~0 (+ (* main_~a~0 2) 1)))} is VALID [2022-04-08 10:56:58,513 INFO L290 TraceCheckUtils]: 6: Hoare triple {209#(and (= (* main_~a~0 2) 0) (= main_~t~0 (+ (* main_~a~0 2) 1)))} assume !false; {209#(and (= (* main_~a~0 2) 0) (= main_~t~0 (+ (* main_~a~0 2) 1)))} is VALID [2022-04-08 10:56:58,514 INFO L272 TraceCheckUtils]: 7: Hoare triple {209#(and (= (* main_~a~0 2) 0) (= main_~t~0 (+ (* main_~a~0 2) 1)))} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {210#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 10:56:58,515 INFO L290 TraceCheckUtils]: 8: Hoare triple {210#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {211#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 10:56:58,516 INFO L290 TraceCheckUtils]: 9: Hoare triple {211#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {205#false} is VALID [2022-04-08 10:56:58,516 INFO L290 TraceCheckUtils]: 10: Hoare triple {205#false} assume !false; {205#false} is VALID [2022-04-08 10:56:58,516 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 10:56:58,516 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 10:56:58,516 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1500324420] [2022-04-08 10:56:58,517 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1500324420] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 10:56:58,517 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 10:56:58,517 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-08 10:56:58,517 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 10:56:58,517 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1072631470] [2022-04-08 10:56:58,517 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1072631470] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 10:56:58,518 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 10:56:58,518 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-08 10:56:58,518 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1530471498] [2022-04-08 10:56:58,518 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 10:56:58,519 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2022-04-08 10:56:58,519 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 10:56:58,519 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 6 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 10:56:58,529 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 11 edges. 11 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:56:58,530 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-08 10:56:58,530 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 10:56:58,531 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-08 10:56:58,531 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-08 10:56:58,531 INFO L87 Difference]: Start difference. First operand 20 states and 25 transitions. Second operand has 6 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 10:56:58,963 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:56:58,964 INFO L93 Difference]: Finished difference Result 34 states and 44 transitions. [2022-04-08 10:56:58,964 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-08 10:56:58,964 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2022-04-08 10:56:58,964 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 10:56:58,964 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 10:56:58,967 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 44 transitions. [2022-04-08 10:56:58,967 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 10:56:58,970 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 44 transitions. [2022-04-08 10:56:58,970 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 7 states and 44 transitions. [2022-04-08 10:56:59,034 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:56:59,039 INFO L225 Difference]: With dead ends: 34 [2022-04-08 10:56:59,039 INFO L226 Difference]: Without dead ends: 32 [2022-04-08 10:56:59,040 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-08 10:56:59,043 INFO L913 BasicCegarLoop]: 17 mSDtfsCounter, 21 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 107 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 81 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-08 10:56:59,044 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [26 Valid, 34 Invalid, 107 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 81 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-08 10:56:59,046 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-08 10:56:59,061 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 30. [2022-04-08 10:56:59,061 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 10:56:59,062 INFO L82 GeneralOperation]: Start isEquivalent. First operand 32 states. Second operand has 30 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 16 states have internal predecessors, (17), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 10:56:59,062 INFO L74 IsIncluded]: Start isIncluded. First operand 32 states. Second operand has 30 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 16 states have internal predecessors, (17), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 10:56:59,062 INFO L87 Difference]: Start difference. First operand 32 states. Second operand has 30 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 16 states have internal predecessors, (17), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 10:56:59,066 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:56:59,067 INFO L93 Difference]: Finished difference Result 32 states and 42 transitions. [2022-04-08 10:56:59,067 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-04-08 10:56:59,068 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 10:56:59,068 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 10:56:59,068 INFO L74 IsIncluded]: Start isIncluded. First operand has 30 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 16 states have internal predecessors, (17), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) Second operand 32 states. [2022-04-08 10:56:59,069 INFO L87 Difference]: Start difference. First operand has 30 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 16 states have internal predecessors, (17), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) Second operand 32 states. [2022-04-08 10:56:59,072 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:56:59,073 INFO L93 Difference]: Finished difference Result 32 states and 42 transitions. [2022-04-08 10:56:59,073 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-04-08 10:56:59,073 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 10:56:59,074 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 10:56:59,074 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 10:56:59,074 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 10:56:59,074 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 16 states have internal predecessors, (17), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-08 10:56:59,077 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2022-04-08 10:56:59,077 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 11 [2022-04-08 10:56:59,077 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 10:56:59,077 INFO L478 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2022-04-08 10:56:59,078 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-08 10:56:59,078 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 30 states and 39 transitions. [2022-04-08 10:56:59,129 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 39 edges. 39 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:56:59,129 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2022-04-08 10:56:59,130 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2022-04-08 10:56:59,130 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 10:56:59,131 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 10:56:59,131 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-08 10:56:59,131 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 10:56:59,132 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 10:56:59,132 INFO L85 PathProgramCache]: Analyzing trace with hash -1248765655, now seen corresponding path program 1 times [2022-04-08 10:56:59,133 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 10:56:59,136 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1999708117] [2022-04-08 10:56:59,138 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 10:56:59,138 INFO L85 PathProgramCache]: Analyzing trace with hash -1248765655, now seen corresponding path program 2 times [2022-04-08 10:56:59,138 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 10:56:59,139 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1657337660] [2022-04-08 10:56:59,139 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 10:56:59,139 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 10:56:59,153 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 10:56:59,153 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [298817971] [2022-04-08 10:56:59,154 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 10:56:59,154 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 10:56:59,154 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 10:56:59,167 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 10:56:59,179 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-08 10:56:59,220 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 10:56:59,221 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 10:56:59,222 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-08 10:56:59,230 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 10:56:59,233 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 10:56:59,348 INFO L272 TraceCheckUtils]: 0: Hoare triple {415#true} call ULTIMATE.init(); {415#true} is VALID [2022-04-08 10:56:59,349 INFO L290 TraceCheckUtils]: 1: Hoare triple {415#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(11, 2);call #Ultimate.allocInit(12, 3); {415#true} is VALID [2022-04-08 10:56:59,349 INFO L290 TraceCheckUtils]: 2: Hoare triple {415#true} assume true; {415#true} is VALID [2022-04-08 10:56:59,349 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {415#true} {415#true} #65#return; {415#true} is VALID [2022-04-08 10:56:59,349 INFO L272 TraceCheckUtils]: 4: Hoare triple {415#true} call #t~ret5 := main(); {415#true} is VALID [2022-04-08 10:56:59,350 INFO L290 TraceCheckUtils]: 5: Hoare triple {415#true} havoc ~n~0;havoc ~a~0;havoc ~s~0;havoc ~t~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~n~0 := #t~nondet4;havoc #t~nondet4;~a~0 := 0;~s~0 := 1;~t~0 := 1; {435#(and (= main_~a~0 0) (= main_~s~0 1))} is VALID [2022-04-08 10:56:59,351 INFO L290 TraceCheckUtils]: 6: Hoare triple {435#(and (= main_~a~0 0) (= main_~s~0 1))} assume !false; {435#(and (= main_~a~0 0) (= main_~s~0 1))} is VALID [2022-04-08 10:56:59,351 INFO L272 TraceCheckUtils]: 7: Hoare triple {435#(and (= main_~a~0 0) (= main_~s~0 1))} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {415#true} is VALID [2022-04-08 10:56:59,351 INFO L290 TraceCheckUtils]: 8: Hoare triple {415#true} ~cond := #in~cond; {415#true} is VALID [2022-04-08 10:56:59,351 INFO L290 TraceCheckUtils]: 9: Hoare triple {415#true} assume !(0 == ~cond); {415#true} is VALID [2022-04-08 10:56:59,352 INFO L290 TraceCheckUtils]: 10: Hoare triple {415#true} assume true; {415#true} is VALID [2022-04-08 10:56:59,352 INFO L284 TraceCheckUtils]: 11: Hoare quadruple {415#true} {435#(and (= main_~a~0 0) (= main_~s~0 1))} #53#return; {435#(and (= main_~a~0 0) (= main_~s~0 1))} is VALID [2022-04-08 10:56:59,353 INFO L272 TraceCheckUtils]: 12: Hoare triple {435#(and (= main_~a~0 0) (= main_~s~0 1))} call __VERIFIER_assert((if ~s~0 == (1 + ~a~0) * (1 + ~a~0) then 1 else 0)); {457#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 10:56:59,354 INFO L290 TraceCheckUtils]: 13: Hoare triple {457#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {461#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 10:56:59,354 INFO L290 TraceCheckUtils]: 14: Hoare triple {461#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {416#false} is VALID [2022-04-08 10:56:59,355 INFO L290 TraceCheckUtils]: 15: Hoare triple {416#false} assume !false; {416#false} is VALID [2022-04-08 10:56:59,355 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-08 10:56:59,355 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 10:56:59,355 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 10:56:59,356 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1657337660] [2022-04-08 10:56:59,356 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 10:56:59,356 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [298817971] [2022-04-08 10:56:59,356 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [298817971] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 10:56:59,356 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 10:56:59,356 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 10:56:59,357 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 10:56:59,357 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1999708117] [2022-04-08 10:56:59,357 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1999708117] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 10:56:59,357 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 10:56:59,357 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 10:56:59,357 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1998667068] [2022-04-08 10:56:59,358 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 10:56:59,358 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 16 [2022-04-08 10:56:59,358 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 10:56:59,358 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 10:56:59,372 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 16 edges. 16 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:56:59,372 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 10:56:59,373 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 10:56:59,373 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 10:56:59,373 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-08 10:56:59,374 INFO L87 Difference]: Start difference. First operand 30 states and 39 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 10:56:59,519 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:56:59,519 INFO L93 Difference]: Finished difference Result 38 states and 47 transitions. [2022-04-08 10:56:59,519 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 10:56:59,520 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 16 [2022-04-08 10:56:59,520 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 10:56:59,520 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 10:56:59,522 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 44 transitions. [2022-04-08 10:56:59,523 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 10:56:59,524 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 44 transitions. [2022-04-08 10:56:59,525 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 44 transitions. [2022-04-08 10:56:59,583 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:56:59,585 INFO L225 Difference]: With dead ends: 38 [2022-04-08 10:56:59,585 INFO L226 Difference]: Without dead ends: 36 [2022-04-08 10:56:59,585 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-08 10:56:59,586 INFO L913 BasicCegarLoop]: 27 mSDtfsCounter, 6 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 10:56:59,586 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 80 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 10:56:59,587 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-04-08 10:56:59,598 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 35. [2022-04-08 10:56:59,598 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 10:56:59,599 INFO L82 GeneralOperation]: Start isEquivalent. First operand 36 states. Second operand has 35 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-08 10:56:59,599 INFO L74 IsIncluded]: Start isIncluded. First operand 36 states. Second operand has 35 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-08 10:56:59,600 INFO L87 Difference]: Start difference. First operand 36 states. Second operand has 35 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-08 10:56:59,602 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:56:59,602 INFO L93 Difference]: Finished difference Result 36 states and 45 transitions. [2022-04-08 10:56:59,603 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 45 transitions. [2022-04-08 10:56:59,603 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 10:56:59,603 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 10:56:59,604 INFO L74 IsIncluded]: Start isIncluded. First operand has 35 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) Second operand 36 states. [2022-04-08 10:56:59,604 INFO L87 Difference]: Start difference. First operand has 35 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) Second operand 36 states. [2022-04-08 10:56:59,606 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:56:59,607 INFO L93 Difference]: Finished difference Result 36 states and 45 transitions. [2022-04-08 10:56:59,607 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 45 transitions. [2022-04-08 10:56:59,607 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 10:56:59,608 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 10:56:59,608 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 10:56:59,608 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 10:56:59,608 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-08 10:56:59,610 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 44 transitions. [2022-04-08 10:56:59,610 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 44 transitions. Word has length 16 [2022-04-08 10:56:59,610 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 10:56:59,611 INFO L478 AbstractCegarLoop]: Abstraction has 35 states and 44 transitions. [2022-04-08 10:56:59,611 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-08 10:56:59,611 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 35 states and 44 transitions. [2022-04-08 10:56:59,667 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:56:59,667 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 44 transitions. [2022-04-08 10:56:59,668 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-04-08 10:56:59,668 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 10:56:59,668 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 10:56:59,699 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-08 10:56:59,891 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 10:56:59,892 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 10:56:59,892 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 10:56:59,893 INFO L85 PathProgramCache]: Analyzing trace with hash 1451064513, now seen corresponding path program 1 times [2022-04-08 10:56:59,893 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 10:56:59,893 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [18422937] [2022-04-08 10:56:59,893 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 10:56:59,893 INFO L85 PathProgramCache]: Analyzing trace with hash 1451064513, now seen corresponding path program 2 times [2022-04-08 10:56:59,894 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 10:56:59,894 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1493961946] [2022-04-08 10:56:59,894 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 10:56:59,894 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 10:56:59,907 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 10:56:59,907 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1106438749] [2022-04-08 10:56:59,908 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 10:56:59,908 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 10:56:59,908 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 10:56:59,914 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 10:56:59,915 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-08 10:56:59,950 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 10:56:59,950 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 10:56:59,951 INFO L263 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-08 10:56:59,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 10:56:59,962 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 10:57:00,078 INFO L272 TraceCheckUtils]: 0: Hoare triple {687#true} call ULTIMATE.init(); {687#true} is VALID [2022-04-08 10:57:00,079 INFO L290 TraceCheckUtils]: 1: Hoare triple {687#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(11, 2);call #Ultimate.allocInit(12, 3); {687#true} is VALID [2022-04-08 10:57:00,079 INFO L290 TraceCheckUtils]: 2: Hoare triple {687#true} assume true; {687#true} is VALID [2022-04-08 10:57:00,079 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {687#true} {687#true} #65#return; {687#true} is VALID [2022-04-08 10:57:00,079 INFO L272 TraceCheckUtils]: 4: Hoare triple {687#true} call #t~ret5 := main(); {687#true} is VALID [2022-04-08 10:57:00,082 INFO L290 TraceCheckUtils]: 5: Hoare triple {687#true} havoc ~n~0;havoc ~a~0;havoc ~s~0;havoc ~t~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~n~0 := #t~nondet4;havoc #t~nondet4;~a~0 := 0;~s~0 := 1;~t~0 := 1; {707#(and (= main_~t~0 1) (= main_~s~0 1))} is VALID [2022-04-08 10:57:00,083 INFO L290 TraceCheckUtils]: 6: Hoare triple {707#(and (= main_~t~0 1) (= main_~s~0 1))} assume !false; {707#(and (= main_~t~0 1) (= main_~s~0 1))} is VALID [2022-04-08 10:57:00,083 INFO L272 TraceCheckUtils]: 7: Hoare triple {707#(and (= main_~t~0 1) (= main_~s~0 1))} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {687#true} is VALID [2022-04-08 10:57:00,083 INFO L290 TraceCheckUtils]: 8: Hoare triple {687#true} ~cond := #in~cond; {687#true} is VALID [2022-04-08 10:57:00,083 INFO L290 TraceCheckUtils]: 9: Hoare triple {687#true} assume !(0 == ~cond); {687#true} is VALID [2022-04-08 10:57:00,084 INFO L290 TraceCheckUtils]: 10: Hoare triple {687#true} assume true; {687#true} is VALID [2022-04-08 10:57:00,085 INFO L284 TraceCheckUtils]: 11: Hoare quadruple {687#true} {707#(and (= main_~t~0 1) (= main_~s~0 1))} #53#return; {707#(and (= main_~t~0 1) (= main_~s~0 1))} is VALID [2022-04-08 10:57:00,085 INFO L272 TraceCheckUtils]: 12: Hoare triple {707#(and (= main_~t~0 1) (= main_~s~0 1))} call __VERIFIER_assert((if ~s~0 == (1 + ~a~0) * (1 + ~a~0) then 1 else 0)); {687#true} is VALID [2022-04-08 10:57:00,085 INFO L290 TraceCheckUtils]: 13: Hoare triple {687#true} ~cond := #in~cond; {687#true} is VALID [2022-04-08 10:57:00,086 INFO L290 TraceCheckUtils]: 14: Hoare triple {687#true} assume !(0 == ~cond); {687#true} is VALID [2022-04-08 10:57:00,086 INFO L290 TraceCheckUtils]: 15: Hoare triple {687#true} assume true; {687#true} is VALID [2022-04-08 10:57:00,087 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {687#true} {707#(and (= main_~t~0 1) (= main_~s~0 1))} #55#return; {707#(and (= main_~t~0 1) (= main_~s~0 1))} is VALID [2022-04-08 10:57:00,087 INFO L272 TraceCheckUtils]: 17: Hoare triple {707#(and (= main_~t~0 1) (= main_~s~0 1))} call __VERIFIER_assert((if 0 == 1 + (~t~0 * ~t~0 - 4 * ~s~0 + 2 * ~t~0) then 1 else 0)); {744#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 10:57:00,088 INFO L290 TraceCheckUtils]: 18: Hoare triple {744#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {748#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 10:57:00,088 INFO L290 TraceCheckUtils]: 19: Hoare triple {748#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {688#false} is VALID [2022-04-08 10:57:00,089 INFO L290 TraceCheckUtils]: 20: Hoare triple {688#false} assume !false; {688#false} is VALID [2022-04-08 10:57:00,089 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-08 10:57:00,089 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 10:57:00,089 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 10:57:00,089 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1493961946] [2022-04-08 10:57:00,090 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 10:57:00,090 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1106438749] [2022-04-08 10:57:00,090 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1106438749] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 10:57:00,090 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 10:57:00,090 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 10:57:00,090 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 10:57:00,091 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [18422937] [2022-04-08 10:57:00,091 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [18422937] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 10:57:00,091 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 10:57:00,091 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 10:57:00,091 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1448323794] [2022-04-08 10:57:00,091 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 10:57:00,092 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 21 [2022-04-08 10:57:00,092 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 10:57:00,092 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 10:57:00,107 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 18 edges. 18 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:57:00,107 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 10:57:00,107 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 10:57:00,108 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 10:57:00,108 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-08 10:57:00,108 INFO L87 Difference]: Start difference. First operand 35 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 10:57:00,264 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:57:00,264 INFO L93 Difference]: Finished difference Result 42 states and 50 transitions. [2022-04-08 10:57:00,264 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 10:57:00,264 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 21 [2022-04-08 10:57:00,265 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 10:57:00,265 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 10:57:00,268 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 44 transitions. [2022-04-08 10:57:00,269 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 10:57:00,270 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 44 transitions. [2022-04-08 10:57:00,270 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 44 transitions. [2022-04-08 10:57:00,313 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:57:00,315 INFO L225 Difference]: With dead ends: 42 [2022-04-08 10:57:00,316 INFO L226 Difference]: Without dead ends: 37 [2022-04-08 10:57:00,316 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-08 10:57:00,320 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 6 mSDsluCounter, 55 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 10:57:00,321 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 83 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 10:57:00,323 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2022-04-08 10:57:00,343 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2022-04-08 10:57:00,343 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 10:57:00,344 INFO L82 GeneralOperation]: Start isEquivalent. First operand 37 states. Second operand has 37 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 11 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 10:57:00,344 INFO L74 IsIncluded]: Start isIncluded. First operand 37 states. Second operand has 37 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 11 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 10:57:00,345 INFO L87 Difference]: Start difference. First operand 37 states. Second operand has 37 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 11 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 10:57:00,348 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:57:00,348 INFO L93 Difference]: Finished difference Result 37 states and 42 transitions. [2022-04-08 10:57:00,348 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 42 transitions. [2022-04-08 10:57:00,350 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 10:57:00,350 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 10:57:00,352 INFO L74 IsIncluded]: Start isIncluded. First operand has 37 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 11 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 37 states. [2022-04-08 10:57:00,352 INFO L87 Difference]: Start difference. First operand has 37 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 11 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 37 states. [2022-04-08 10:57:00,359 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:57:00,360 INFO L93 Difference]: Finished difference Result 37 states and 42 transitions. [2022-04-08 10:57:00,360 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 42 transitions. [2022-04-08 10:57:00,362 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 10:57:00,362 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 10:57:00,362 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 10:57:00,362 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 10:57:00,363 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 11 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 10:57:00,365 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 42 transitions. [2022-04-08 10:57:00,365 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 42 transitions. Word has length 21 [2022-04-08 10:57:00,366 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 10:57:00,366 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 42 transitions. [2022-04-08 10:57:00,366 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-08 10:57:00,366 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 37 states and 42 transitions. [2022-04-08 10:57:00,412 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 42 edges. 42 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:57:00,412 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 42 transitions. [2022-04-08 10:57:00,414 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-08 10:57:00,414 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 10:57:00,414 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 10:57:00,441 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-08 10:57:00,638 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,SelfDestructingSolverStorable3 [2022-04-08 10:57:00,639 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 10:57:00,639 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 10:57:00,639 INFO L85 PathProgramCache]: Analyzing trace with hash 412610311, now seen corresponding path program 1 times [2022-04-08 10:57:00,639 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 10:57:00,640 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [238488287] [2022-04-08 10:57:00,901 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-08 10:57:00,901 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 10:57:00,901 INFO L85 PathProgramCache]: Analyzing trace with hash 412610311, now seen corresponding path program 2 times [2022-04-08 10:57:00,901 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 10:57:00,902 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [698495097] [2022-04-08 10:57:00,902 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 10:57:00,902 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 10:57:00,912 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 10:57:00,912 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1417181862] [2022-04-08 10:57:00,912 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 10:57:00,913 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 10:57:00,913 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 10:57:00,914 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 10:57:00,915 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-08 10:57:00,959 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 10:57:00,959 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 10:57:00,960 INFO L263 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-08 10:57:00,969 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 10:57:00,975 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 10:57:01,125 INFO L272 TraceCheckUtils]: 0: Hoare triple {988#true} call ULTIMATE.init(); {988#true} is VALID [2022-04-08 10:57:01,127 INFO L290 TraceCheckUtils]: 1: Hoare triple {988#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(11, 2);call #Ultimate.allocInit(12, 3); {988#true} is VALID [2022-04-08 10:57:01,127 INFO L290 TraceCheckUtils]: 2: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-08 10:57:01,127 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {988#true} {988#true} #65#return; {988#true} is VALID [2022-04-08 10:57:01,127 INFO L272 TraceCheckUtils]: 4: Hoare triple {988#true} call #t~ret5 := main(); {988#true} is VALID [2022-04-08 10:57:01,128 INFO L290 TraceCheckUtils]: 5: Hoare triple {988#true} havoc ~n~0;havoc ~a~0;havoc ~s~0;havoc ~t~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~n~0 := #t~nondet4;havoc #t~nondet4;~a~0 := 0;~s~0 := 1;~t~0 := 1; {1008#(and (= main_~a~0 0) (= main_~t~0 1))} is VALID [2022-04-08 10:57:01,128 INFO L290 TraceCheckUtils]: 6: Hoare triple {1008#(and (= main_~a~0 0) (= main_~t~0 1))} assume !false; {1008#(and (= main_~a~0 0) (= main_~t~0 1))} is VALID [2022-04-08 10:57:01,129 INFO L272 TraceCheckUtils]: 7: Hoare triple {1008#(and (= main_~a~0 0) (= main_~t~0 1))} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {988#true} is VALID [2022-04-08 10:57:01,129 INFO L290 TraceCheckUtils]: 8: Hoare triple {988#true} ~cond := #in~cond; {988#true} is VALID [2022-04-08 10:57:01,129 INFO L290 TraceCheckUtils]: 9: Hoare triple {988#true} assume !(0 == ~cond); {988#true} is VALID [2022-04-08 10:57:01,129 INFO L290 TraceCheckUtils]: 10: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-08 10:57:01,130 INFO L284 TraceCheckUtils]: 11: Hoare quadruple {988#true} {1008#(and (= main_~a~0 0) (= main_~t~0 1))} #53#return; {1008#(and (= main_~a~0 0) (= main_~t~0 1))} is VALID [2022-04-08 10:57:01,130 INFO L272 TraceCheckUtils]: 12: Hoare triple {1008#(and (= main_~a~0 0) (= main_~t~0 1))} call __VERIFIER_assert((if ~s~0 == (1 + ~a~0) * (1 + ~a~0) then 1 else 0)); {988#true} is VALID [2022-04-08 10:57:01,130 INFO L290 TraceCheckUtils]: 13: Hoare triple {988#true} ~cond := #in~cond; {988#true} is VALID [2022-04-08 10:57:01,131 INFO L290 TraceCheckUtils]: 14: Hoare triple {988#true} assume !(0 == ~cond); {988#true} is VALID [2022-04-08 10:57:01,131 INFO L290 TraceCheckUtils]: 15: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-08 10:57:01,131 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {988#true} {1008#(and (= main_~a~0 0) (= main_~t~0 1))} #55#return; {1008#(and (= main_~a~0 0) (= main_~t~0 1))} is VALID [2022-04-08 10:57:01,132 INFO L272 TraceCheckUtils]: 17: Hoare triple {1008#(and (= main_~a~0 0) (= main_~t~0 1))} call __VERIFIER_assert((if 0 == 1 + (~t~0 * ~t~0 - 4 * ~s~0 + 2 * ~t~0) then 1 else 0)); {988#true} is VALID [2022-04-08 10:57:01,132 INFO L290 TraceCheckUtils]: 18: Hoare triple {988#true} ~cond := #in~cond; {988#true} is VALID [2022-04-08 10:57:01,133 INFO L290 TraceCheckUtils]: 19: Hoare triple {988#true} assume !(0 == ~cond); {988#true} is VALID [2022-04-08 10:57:01,133 INFO L290 TraceCheckUtils]: 20: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-08 10:57:01,133 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {988#true} {1008#(and (= main_~a~0 0) (= main_~t~0 1))} #57#return; {1008#(and (= main_~a~0 0) (= main_~t~0 1))} is VALID [2022-04-08 10:57:01,134 INFO L290 TraceCheckUtils]: 22: Hoare triple {1008#(and (= main_~a~0 0) (= main_~t~0 1))} assume !!(~s~0 <= ~n~0);~a~0 := 1 + ~a~0;~t~0 := 2 + ~t~0;~s~0 := ~s~0 + ~t~0; {1060#(and (= (+ (- 2) main_~t~0) 1) (= (+ (- 1) main_~a~0) 0))} is VALID [2022-04-08 10:57:01,135 INFO L290 TraceCheckUtils]: 23: Hoare triple {1060#(and (= (+ (- 2) main_~t~0) 1) (= (+ (- 1) main_~a~0) 0))} assume !false; {1060#(and (= (+ (- 2) main_~t~0) 1) (= (+ (- 1) main_~a~0) 0))} is VALID [2022-04-08 10:57:01,136 INFO L272 TraceCheckUtils]: 24: Hoare triple {1060#(and (= (+ (- 2) main_~t~0) 1) (= (+ (- 1) main_~a~0) 0))} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {1067#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 10:57:01,141 INFO L290 TraceCheckUtils]: 25: Hoare triple {1067#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1071#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 10:57:01,142 INFO L290 TraceCheckUtils]: 26: Hoare triple {1071#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {989#false} is VALID [2022-04-08 10:57:01,143 INFO L290 TraceCheckUtils]: 27: Hoare triple {989#false} assume !false; {989#false} is VALID [2022-04-08 10:57:01,143 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-08 10:57:01,143 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-08 10:57:01,285 INFO L290 TraceCheckUtils]: 27: Hoare triple {989#false} assume !false; {989#false} is VALID [2022-04-08 10:57:01,286 INFO L290 TraceCheckUtils]: 26: Hoare triple {1071#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {989#false} is VALID [2022-04-08 10:57:01,286 INFO L290 TraceCheckUtils]: 25: Hoare triple {1067#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1071#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 10:57:01,287 INFO L272 TraceCheckUtils]: 24: Hoare triple {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {1067#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 10:57:01,287 INFO L290 TraceCheckUtils]: 23: Hoare triple {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} assume !false; {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} is VALID [2022-04-08 10:57:01,288 INFO L290 TraceCheckUtils]: 22: Hoare triple {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} assume !!(~s~0 <= ~n~0);~a~0 := 1 + ~a~0;~t~0 := 2 + ~t~0;~s~0 := ~s~0 + ~t~0; {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} is VALID [2022-04-08 10:57:01,289 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {988#true} {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} #57#return; {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} is VALID [2022-04-08 10:57:01,289 INFO L290 TraceCheckUtils]: 20: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-08 10:57:01,289 INFO L290 TraceCheckUtils]: 19: Hoare triple {988#true} assume !(0 == ~cond); {988#true} is VALID [2022-04-08 10:57:01,289 INFO L290 TraceCheckUtils]: 18: Hoare triple {988#true} ~cond := #in~cond; {988#true} is VALID [2022-04-08 10:57:01,289 INFO L272 TraceCheckUtils]: 17: Hoare triple {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} call __VERIFIER_assert((if 0 == 1 + (~t~0 * ~t~0 - 4 * ~s~0 + 2 * ~t~0) then 1 else 0)); {988#true} is VALID [2022-04-08 10:57:01,292 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {988#true} {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} #55#return; {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} is VALID [2022-04-08 10:57:01,292 INFO L290 TraceCheckUtils]: 15: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-08 10:57:01,292 INFO L290 TraceCheckUtils]: 14: Hoare triple {988#true} assume !(0 == ~cond); {988#true} is VALID [2022-04-08 10:57:01,293 INFO L290 TraceCheckUtils]: 13: Hoare triple {988#true} ~cond := #in~cond; {988#true} is VALID [2022-04-08 10:57:01,293 INFO L272 TraceCheckUtils]: 12: Hoare triple {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} call __VERIFIER_assert((if ~s~0 == (1 + ~a~0) * (1 + ~a~0) then 1 else 0)); {988#true} is VALID [2022-04-08 10:57:01,293 INFO L284 TraceCheckUtils]: 11: Hoare quadruple {988#true} {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} #53#return; {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} is VALID [2022-04-08 10:57:01,294 INFO L290 TraceCheckUtils]: 10: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-08 10:57:01,294 INFO L290 TraceCheckUtils]: 9: Hoare triple {988#true} assume !(0 == ~cond); {988#true} is VALID [2022-04-08 10:57:01,294 INFO L290 TraceCheckUtils]: 8: Hoare triple {988#true} ~cond := #in~cond; {988#true} is VALID [2022-04-08 10:57:01,294 INFO L272 TraceCheckUtils]: 7: Hoare triple {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {988#true} is VALID [2022-04-08 10:57:01,295 INFO L290 TraceCheckUtils]: 6: Hoare triple {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} assume !false; {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} is VALID [2022-04-08 10:57:01,295 INFO L290 TraceCheckUtils]: 5: Hoare triple {988#true} havoc ~n~0;havoc ~a~0;havoc ~s~0;havoc ~t~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~n~0 := #t~nondet4;havoc #t~nondet4;~a~0 := 0;~s~0 := 1;~t~0 := 1; {1087#(= main_~t~0 (+ (* main_~a~0 2) 1))} is VALID [2022-04-08 10:57:01,296 INFO L272 TraceCheckUtils]: 4: Hoare triple {988#true} call #t~ret5 := main(); {988#true} is VALID [2022-04-08 10:57:01,296 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {988#true} {988#true} #65#return; {988#true} is VALID [2022-04-08 10:57:01,296 INFO L290 TraceCheckUtils]: 2: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-08 10:57:01,296 INFO L290 TraceCheckUtils]: 1: Hoare triple {988#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(11, 2);call #Ultimate.allocInit(12, 3); {988#true} is VALID [2022-04-08 10:57:01,296 INFO L272 TraceCheckUtils]: 0: Hoare triple {988#true} call ULTIMATE.init(); {988#true} is VALID [2022-04-08 10:57:01,297 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2022-04-08 10:57:01,297 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 10:57:01,297 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [698495097] [2022-04-08 10:57:01,297 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 10:57:01,297 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1417181862] [2022-04-08 10:57:01,297 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1417181862] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-08 10:57:01,298 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-08 10:57:01,298 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-08 10:57:01,298 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 10:57:01,298 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [238488287] [2022-04-08 10:57:01,298 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [238488287] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 10:57:01,298 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 10:57:01,298 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 10:57:01,298 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [860251326] [2022-04-08 10:57:01,299 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 10:57:01,299 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-08 10:57:01,299 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 10:57:01,299 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 10:57:01,317 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 21 edges. 21 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:57:01,317 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 10:57:01,317 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 10:57:01,318 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 10:57:01,318 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-08 10:57:01,318 INFO L87 Difference]: Start difference. First operand 37 states and 42 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 10:57:01,482 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:57:01,482 INFO L93 Difference]: Finished difference Result 43 states and 47 transitions. [2022-04-08 10:57:01,482 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 10:57:01,482 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-08 10:57:01,483 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 10:57:01,483 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 10:57:01,485 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 30 transitions. [2022-04-08 10:57:01,485 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 10:57:01,486 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 30 transitions. [2022-04-08 10:57:01,486 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 30 transitions. [2022-04-08 10:57:01,518 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-08 10:57:01,519 INFO L225 Difference]: With dead ends: 43 [2022-04-08 10:57:01,519 INFO L226 Difference]: Without dead ends: 41 [2022-04-08 10:57:01,519 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 48 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-08 10:57:01,520 INFO L913 BasicCegarLoop]: 20 mSDtfsCounter, 6 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 10:57:01,520 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 56 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 10:57:01,521 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-04-08 10:57:01,541 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-04-08 10:57:01,541 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 10:57:01,541 INFO L82 GeneralOperation]: Start isEquivalent. First operand 41 states. Second operand has 41 states, 23 states have (on average 1.0869565217391304) internal successors, (25), 24 states have internal predecessors, (25), 11 states have call successors, (11), 7 states have call predecessors, (11), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 10:57:01,541 INFO L74 IsIncluded]: Start isIncluded. First operand 41 states. Second operand has 41 states, 23 states have (on average 1.0869565217391304) internal successors, (25), 24 states have internal predecessors, (25), 11 states have call successors, (11), 7 states have call predecessors, (11), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 10:57:01,542 INFO L87 Difference]: Start difference. First operand 41 states. Second operand has 41 states, 23 states have (on average 1.0869565217391304) internal successors, (25), 24 states have internal predecessors, (25), 11 states have call successors, (11), 7 states have call predecessors, (11), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 10:57:01,543 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:57:01,543 INFO L93 Difference]: Finished difference Result 41 states and 45 transitions. [2022-04-08 10:57:01,543 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-08 10:57:01,544 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 10:57:01,544 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 10:57:01,544 INFO L74 IsIncluded]: Start isIncluded. First operand has 41 states, 23 states have (on average 1.0869565217391304) internal successors, (25), 24 states have internal predecessors, (25), 11 states have call successors, (11), 7 states have call predecessors, (11), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 41 states. [2022-04-08 10:57:01,544 INFO L87 Difference]: Start difference. First operand has 41 states, 23 states have (on average 1.0869565217391304) internal successors, (25), 24 states have internal predecessors, (25), 11 states have call successors, (11), 7 states have call predecessors, (11), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 41 states. [2022-04-08 10:57:01,546 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:57:01,546 INFO L93 Difference]: Finished difference Result 41 states and 45 transitions. [2022-04-08 10:57:01,546 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-08 10:57:01,546 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 10:57:01,546 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 10:57:01,547 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 10:57:01,547 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 10:57:01,547 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 23 states have (on average 1.0869565217391304) internal successors, (25), 24 states have internal predecessors, (25), 11 states have call successors, (11), 7 states have call predecessors, (11), 6 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 10:57:01,548 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 45 transitions. [2022-04-08 10:57:01,548 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 45 transitions. Word has length 28 [2022-04-08 10:57:01,549 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 10:57:01,549 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 45 transitions. [2022-04-08 10:57:01,549 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 10:57:01,549 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 41 states and 45 transitions. [2022-04-08 10:57:01,600 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 45 edges. 45 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:57:01,600 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-08 10:57:01,600 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-04-08 10:57:01,600 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 10:57:01,601 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 10:57:01,621 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-08 10:57:01,807 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 10:57:01,808 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 10:57:01,808 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 10:57:01,808 INFO L85 PathProgramCache]: Analyzing trace with hash -1543321117, now seen corresponding path program 3 times [2022-04-08 10:57:01,808 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 10:57:01,809 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1278018578] [2022-04-08 10:57:02,034 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-08 10:57:02,034 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-08 10:57:02,034 INFO L85 PathProgramCache]: Analyzing trace with hash -1543321117, now seen corresponding path program 4 times [2022-04-08 10:57:02,034 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 10:57:02,034 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2143680922] [2022-04-08 10:57:02,035 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 10:57:02,035 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 10:57:02,044 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 10:57:02,044 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [202051145] [2022-04-08 10:57:02,044 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-08 10:57:02,044 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 10:57:02,044 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 10:57:02,045 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 10:57:02,052 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-08 10:57:02,107 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-08 10:57:02,108 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 10:57:02,109 INFO L263 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 24 conjunts are in the unsatisfiable core [2022-04-08 10:57:02,200 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 10:57:02,201 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 10:57:02,516 INFO L272 TraceCheckUtils]: 0: Hoare triple {1414#true} call ULTIMATE.init(); {1414#true} is VALID [2022-04-08 10:57:02,517 INFO L290 TraceCheckUtils]: 1: Hoare triple {1414#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(11, 2);call #Ultimate.allocInit(12, 3); {1414#true} is VALID [2022-04-08 10:57:02,517 INFO L290 TraceCheckUtils]: 2: Hoare triple {1414#true} assume true; {1414#true} is VALID [2022-04-08 10:57:02,517 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1414#true} {1414#true} #65#return; {1414#true} is VALID [2022-04-08 10:57:02,517 INFO L272 TraceCheckUtils]: 4: Hoare triple {1414#true} call #t~ret5 := main(); {1414#true} is VALID [2022-04-08 10:57:02,517 INFO L290 TraceCheckUtils]: 5: Hoare triple {1414#true} havoc ~n~0;havoc ~a~0;havoc ~s~0;havoc ~t~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~n~0 := #t~nondet4;havoc #t~nondet4;~a~0 := 0;~s~0 := 1;~t~0 := 1; {1414#true} is VALID [2022-04-08 10:57:02,518 INFO L290 TraceCheckUtils]: 6: Hoare triple {1414#true} assume !false; {1414#true} is VALID [2022-04-08 10:57:02,518 INFO L272 TraceCheckUtils]: 7: Hoare triple {1414#true} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {1414#true} is VALID [2022-04-08 10:57:02,518 INFO L290 TraceCheckUtils]: 8: Hoare triple {1414#true} ~cond := #in~cond; {1414#true} is VALID [2022-04-08 10:57:02,518 INFO L290 TraceCheckUtils]: 9: Hoare triple {1414#true} assume !(0 == ~cond); {1414#true} is VALID [2022-04-08 10:57:02,518 INFO L290 TraceCheckUtils]: 10: Hoare triple {1414#true} assume true; {1414#true} is VALID [2022-04-08 10:57:02,518 INFO L284 TraceCheckUtils]: 11: Hoare quadruple {1414#true} {1414#true} #53#return; {1414#true} is VALID [2022-04-08 10:57:02,519 INFO L272 TraceCheckUtils]: 12: Hoare triple {1414#true} call __VERIFIER_assert((if ~s~0 == (1 + ~a~0) * (1 + ~a~0) then 1 else 0)); {1414#true} is VALID [2022-04-08 10:57:02,527 INFO L290 TraceCheckUtils]: 13: Hoare triple {1414#true} ~cond := #in~cond; {1458#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-08 10:57:02,528 INFO L290 TraceCheckUtils]: 14: Hoare triple {1458#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 10:57:02,529 INFO L290 TraceCheckUtils]: 15: Hoare triple {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 10:57:02,529 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} {1414#true} #55#return; {1469#(= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0)} is VALID [2022-04-08 10:57:02,530 INFO L272 TraceCheckUtils]: 17: Hoare triple {1469#(= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0)} call __VERIFIER_assert((if 0 == 1 + (~t~0 * ~t~0 - 4 * ~s~0 + 2 * ~t~0) then 1 else 0)); {1414#true} is VALID [2022-04-08 10:57:02,530 INFO L290 TraceCheckUtils]: 18: Hoare triple {1414#true} ~cond := #in~cond; {1458#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-08 10:57:02,531 INFO L290 TraceCheckUtils]: 19: Hoare triple {1458#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 10:57:02,531 INFO L290 TraceCheckUtils]: 20: Hoare triple {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 10:57:02,532 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} {1469#(= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0)} #57#return; {1485#(and (= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0) (= (+ (* main_~t~0 2) (* main_~t~0 main_~t~0) 1) (* main_~s~0 4)))} is VALID [2022-04-08 10:57:02,536 INFO L290 TraceCheckUtils]: 22: Hoare triple {1485#(and (= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0) (= (+ (* main_~t~0 2) (* main_~t~0 main_~t~0) 1) (* main_~s~0 4)))} assume !!(~s~0 <= ~n~0);~a~0 := 1 + ~a~0;~t~0 := 2 + ~t~0;~s~0 := ~s~0 + ~t~0; {1489#(and (= (+ (* (* (+ (- 1) main_~a~0) (+ (- 1) main_~a~0)) 4) (- 4) (* main_~a~0 8)) (+ (- 3) (* main_~t~0 2) (* (+ (- 2) main_~t~0) (+ (- 2) main_~t~0)))) (= (+ (- 1) (* main_~a~0 2) main_~t~0 (* (+ (- 1) main_~a~0) (+ (- 1) main_~a~0))) main_~s~0))} is VALID [2022-04-08 10:57:02,536 INFO L290 TraceCheckUtils]: 23: Hoare triple {1489#(and (= (+ (* (* (+ (- 1) main_~a~0) (+ (- 1) main_~a~0)) 4) (- 4) (* main_~a~0 8)) (+ (- 3) (* main_~t~0 2) (* (+ (- 2) main_~t~0) (+ (- 2) main_~t~0)))) (= (+ (- 1) (* main_~a~0 2) main_~t~0 (* (+ (- 1) main_~a~0) (+ (- 1) main_~a~0))) main_~s~0))} assume !false; {1489#(and (= (+ (* (* (+ (- 1) main_~a~0) (+ (- 1) main_~a~0)) 4) (- 4) (* main_~a~0 8)) (+ (- 3) (* main_~t~0 2) (* (+ (- 2) main_~t~0) (+ (- 2) main_~t~0)))) (= (+ (- 1) (* main_~a~0 2) main_~t~0 (* (+ (- 1) main_~a~0) (+ (- 1) main_~a~0))) main_~s~0))} is VALID [2022-04-08 10:57:02,537 INFO L272 TraceCheckUtils]: 24: Hoare triple {1489#(and (= (+ (* (* (+ (- 1) main_~a~0) (+ (- 1) main_~a~0)) 4) (- 4) (* main_~a~0 8)) (+ (- 3) (* main_~t~0 2) (* (+ (- 2) main_~t~0) (+ (- 2) main_~t~0)))) (= (+ (- 1) (* main_~a~0 2) main_~t~0 (* (+ (- 1) main_~a~0) (+ (- 1) main_~a~0))) main_~s~0))} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {1414#true} is VALID [2022-04-08 10:57:02,537 INFO L290 TraceCheckUtils]: 25: Hoare triple {1414#true} ~cond := #in~cond; {1458#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-08 10:57:02,537 INFO L290 TraceCheckUtils]: 26: Hoare triple {1458#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 10:57:02,537 INFO L290 TraceCheckUtils]: 27: Hoare triple {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 10:57:02,538 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} {1489#(and (= (+ (* (* (+ (- 1) main_~a~0) (+ (- 1) main_~a~0)) 4) (- 4) (* main_~a~0 8)) (+ (- 3) (* main_~t~0 2) (* (+ (- 2) main_~t~0) (+ (- 2) main_~t~0)))) (= (+ (- 1) (* main_~a~0 2) main_~t~0 (* (+ (- 1) main_~a~0) (+ (- 1) main_~a~0))) main_~s~0))} #53#return; {1469#(= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0)} is VALID [2022-04-08 10:57:02,539 INFO L272 TraceCheckUtils]: 29: Hoare triple {1469#(= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0)} call __VERIFIER_assert((if ~s~0 == (1 + ~a~0) * (1 + ~a~0) then 1 else 0)); {1511#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 10:57:02,539 INFO L290 TraceCheckUtils]: 30: Hoare triple {1511#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1515#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 10:57:02,540 INFO L290 TraceCheckUtils]: 31: Hoare triple {1515#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1415#false} is VALID [2022-04-08 10:57:02,540 INFO L290 TraceCheckUtils]: 32: Hoare triple {1415#false} assume !false; {1415#false} is VALID [2022-04-08 10:57:02,540 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 17 proven. 3 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-04-08 10:57:02,540 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-08 10:57:03,169 INFO L290 TraceCheckUtils]: 32: Hoare triple {1415#false} assume !false; {1415#false} is VALID [2022-04-08 10:57:03,170 INFO L290 TraceCheckUtils]: 31: Hoare triple {1515#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1415#false} is VALID [2022-04-08 10:57:03,170 INFO L290 TraceCheckUtils]: 30: Hoare triple {1511#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1515#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 10:57:03,171 INFO L272 TraceCheckUtils]: 29: Hoare triple {1469#(= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0)} call __VERIFIER_assert((if ~s~0 == (1 + ~a~0) * (1 + ~a~0) then 1 else 0)); {1511#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 10:57:03,172 INFO L284 TraceCheckUtils]: 28: Hoare quadruple {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} {1534#(or (not (= main_~t~0 (+ (* main_~a~0 2) 1))) (= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0))} #53#return; {1469#(= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0)} is VALID [2022-04-08 10:57:03,172 INFO L290 TraceCheckUtils]: 27: Hoare triple {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 10:57:03,173 INFO L290 TraceCheckUtils]: 26: Hoare triple {1544#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 10:57:03,173 INFO L290 TraceCheckUtils]: 25: Hoare triple {1414#true} ~cond := #in~cond; {1544#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 10:57:03,173 INFO L272 TraceCheckUtils]: 24: Hoare triple {1534#(or (not (= main_~t~0 (+ (* main_~a~0 2) 1))) (= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0))} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {1414#true} is VALID [2022-04-08 10:57:03,174 INFO L290 TraceCheckUtils]: 23: Hoare triple {1534#(or (not (= main_~t~0 (+ (* main_~a~0 2) 1))) (= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0))} assume !false; {1534#(or (not (= main_~t~0 (+ (* main_~a~0 2) 1))) (= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0))} is VALID [2022-04-08 10:57:03,176 INFO L290 TraceCheckUtils]: 22: Hoare triple {1534#(or (not (= main_~t~0 (+ (* main_~a~0 2) 1))) (= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0))} assume !!(~s~0 <= ~n~0);~a~0 := 1 + ~a~0;~t~0 := 2 + ~t~0;~s~0 := ~s~0 + ~t~0; {1534#(or (not (= main_~t~0 (+ (* main_~a~0 2) 1))) (= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0))} is VALID [2022-04-08 10:57:03,178 INFO L284 TraceCheckUtils]: 21: Hoare quadruple {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} {1414#true} #57#return; {1534#(or (not (= main_~t~0 (+ (* main_~a~0 2) 1))) (= (+ (* main_~a~0 2) (* main_~a~0 main_~a~0) 1) main_~s~0))} is VALID [2022-04-08 10:57:03,179 INFO L290 TraceCheckUtils]: 20: Hoare triple {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 10:57:03,179 INFO L290 TraceCheckUtils]: 19: Hoare triple {1544#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {1462#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 10:57:03,180 INFO L290 TraceCheckUtils]: 18: Hoare triple {1414#true} ~cond := #in~cond; {1544#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 10:57:03,180 INFO L272 TraceCheckUtils]: 17: Hoare triple {1414#true} call __VERIFIER_assert((if 0 == 1 + (~t~0 * ~t~0 - 4 * ~s~0 + 2 * ~t~0) then 1 else 0)); {1414#true} is VALID [2022-04-08 10:57:03,180 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1414#true} {1414#true} #55#return; {1414#true} is VALID [2022-04-08 10:57:03,180 INFO L290 TraceCheckUtils]: 15: Hoare triple {1414#true} assume true; {1414#true} is VALID [2022-04-08 10:57:03,180 INFO L290 TraceCheckUtils]: 14: Hoare triple {1414#true} assume !(0 == ~cond); {1414#true} is VALID [2022-04-08 10:57:03,180 INFO L290 TraceCheckUtils]: 13: Hoare triple {1414#true} ~cond := #in~cond; {1414#true} is VALID [2022-04-08 10:57:03,181 INFO L272 TraceCheckUtils]: 12: Hoare triple {1414#true} call __VERIFIER_assert((if ~s~0 == (1 + ~a~0) * (1 + ~a~0) then 1 else 0)); {1414#true} is VALID [2022-04-08 10:57:03,181 INFO L284 TraceCheckUtils]: 11: Hoare quadruple {1414#true} {1414#true} #53#return; {1414#true} is VALID [2022-04-08 10:57:03,181 INFO L290 TraceCheckUtils]: 10: Hoare triple {1414#true} assume true; {1414#true} is VALID [2022-04-08 10:57:03,181 INFO L290 TraceCheckUtils]: 9: Hoare triple {1414#true} assume !(0 == ~cond); {1414#true} is VALID [2022-04-08 10:57:03,181 INFO L290 TraceCheckUtils]: 8: Hoare triple {1414#true} ~cond := #in~cond; {1414#true} is VALID [2022-04-08 10:57:03,181 INFO L272 TraceCheckUtils]: 7: Hoare triple {1414#true} call __VERIFIER_assert((if ~t~0 == 1 + 2 * ~a~0 then 1 else 0)); {1414#true} is VALID [2022-04-08 10:57:03,182 INFO L290 TraceCheckUtils]: 6: Hoare triple {1414#true} assume !false; {1414#true} is VALID [2022-04-08 10:57:03,182 INFO L290 TraceCheckUtils]: 5: Hoare triple {1414#true} havoc ~n~0;havoc ~a~0;havoc ~s~0;havoc ~t~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~n~0 := #t~nondet4;havoc #t~nondet4;~a~0 := 0;~s~0 := 1;~t~0 := 1; {1414#true} is VALID [2022-04-08 10:57:03,182 INFO L272 TraceCheckUtils]: 4: Hoare triple {1414#true} call #t~ret5 := main(); {1414#true} is VALID [2022-04-08 10:57:03,182 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1414#true} {1414#true} #65#return; {1414#true} is VALID [2022-04-08 10:57:03,182 INFO L290 TraceCheckUtils]: 2: Hoare triple {1414#true} assume true; {1414#true} is VALID [2022-04-08 10:57:03,182 INFO L290 TraceCheckUtils]: 1: Hoare triple {1414#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(11, 2);call #Ultimate.allocInit(12, 3); {1414#true} is VALID [2022-04-08 10:57:03,182 INFO L272 TraceCheckUtils]: 0: Hoare triple {1414#true} call ULTIMATE.init(); {1414#true} is VALID [2022-04-08 10:57:03,183 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 21 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-08 10:57:03,183 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 10:57:03,183 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2143680922] [2022-04-08 10:57:03,183 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 10:57:03,183 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [202051145] [2022-04-08 10:57:03,183 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [202051145] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-08 10:57:03,184 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-08 10:57:03,184 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 11 [2022-04-08 10:57:03,184 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 10:57:03,184 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1278018578] [2022-04-08 10:57:03,184 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1278018578] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 10:57:03,184 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 10:57:03,184 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-08 10:57:03,184 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [468409804] [2022-04-08 10:57:03,185 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 10:57:03,185 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 33 [2022-04-08 10:57:03,185 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 10:57:03,185 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-08 10:57:03,210 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 27 edges. 27 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:57:03,211 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-08 10:57:03,211 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 10:57:03,211 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-08 10:57:03,211 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-04-08 10:57:03,212 INFO L87 Difference]: Start difference. First operand 41 states and 45 transitions. Second operand has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-08 10:57:03,858 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:57:03,859 INFO L93 Difference]: Finished difference Result 41 states and 45 transitions. [2022-04-08 10:57:03,859 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 10:57:03,859 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 33 [2022-04-08 10:57:03,859 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 10:57:03,859 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-08 10:57:03,860 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 25 transitions. [2022-04-08 10:57:03,860 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-08 10:57:03,861 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 25 transitions. [2022-04-08 10:57:03,861 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 25 transitions. [2022-04-08 10:57:03,899 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 25 edges. 25 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 10:57:03,899 INFO L225 Difference]: With dead ends: 41 [2022-04-08 10:57:03,899 INFO L226 Difference]: Without dead ends: 0 [2022-04-08 10:57:03,900 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 55 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=116, Unknown=0, NotChecked=0, Total=156 [2022-04-08 10:57:03,900 INFO L913 BasicCegarLoop]: 14 mSDtfsCounter, 12 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 54 SdHoareTripleChecker+Invalid, 88 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 65 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-08 10:57:03,901 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 54 Invalid, 88 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-08 10:57:03,905 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-08 10:57:03,905 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-08 10:57:03,905 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 10:57:03,906 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-08 10:57:03,906 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-08 10:57:03,906 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-08 10:57:03,906 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:57:03,906 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-08 10:57:03,906 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-08 10:57:03,906 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 10:57:03,906 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 10:57:03,907 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-08 10:57:03,907 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-08 10:57:03,907 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 10:57:03,907 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-08 10:57:03,907 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-08 10:57:03,907 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 10:57:03,907 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 10:57:03,907 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 10:57:03,907 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 10:57:03,907 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-08 10:57:03,907 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-08 10:57:03,907 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 33 [2022-04-08 10:57:03,907 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 10:57:03,908 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-08 10:57:03,908 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 1.875) internal successors, (15), 6 states have internal predecessors, (15), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-08 10:57:03,908 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 0 states and 0 transitions. [2022-04-08 10:57:03,908 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-08 10:57:03,908 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-08 10:57:03,908 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 10:57:03,910 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-08 10:57:03,930 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2022-04-08 10:57:04,111 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 10:57:04,113 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-04-08 10:57:04,448 INFO L882 garLoopResultBuilder]: For program point reach_errorEXIT(line 5) no Hoare annotation was computed. [2022-04-08 10:57:04,449 INFO L882 garLoopResultBuilder]: For program point reach_errorENTRY(line 5) no Hoare annotation was computed. [2022-04-08 10:57:04,449 INFO L882 garLoopResultBuilder]: For program point reach_errorFINAL(line 5) no Hoare annotation was computed. [2022-04-08 10:57:04,449 INFO L882 garLoopResultBuilder]: For program point assume_abort_if_notENTRY(lines 8 10) no Hoare annotation was computed. [2022-04-08 10:57:04,449 INFO L882 garLoopResultBuilder]: For program point L9(line 9) no Hoare annotation was computed. [2022-04-08 10:57:04,449 INFO L882 garLoopResultBuilder]: For program point L9-2(lines 8 10) no Hoare annotation was computed. [2022-04-08 10:57:04,449 INFO L882 garLoopResultBuilder]: For program point assume_abort_if_notEXIT(lines 8 10) no Hoare annotation was computed. [2022-04-08 10:57:04,449 INFO L878 garLoopResultBuilder]: At program point L32(lines 29 41) the Hoare annotation is: (and (= main_~s~0 (+ main_~t~0 (* main_~a~0 main_~a~0))) (= main_~t~0 (+ (* main_~a~0 2) 1))) [2022-04-08 10:57:04,450 INFO L878 garLoopResultBuilder]: At program point L31(line 31) the Hoare annotation is: (and (= main_~s~0 (+ main_~t~0 (* main_~a~0 main_~a~0))) (= main_~t~0 (+ (* main_~a~0 2) 1))) [2022-04-08 10:57:04,450 INFO L878 garLoopResultBuilder]: At program point L30(line 30) the Hoare annotation is: (and (= main_~s~0 (+ main_~t~0 (* main_~a~0 main_~a~0))) (= main_~t~0 (+ (* main_~a~0 2) 1))) [2022-04-08 10:57:04,450 INFO L885 garLoopResultBuilder]: At program point mainENTRY(lines 20 48) the Hoare annotation is: true [2022-04-08 10:57:04,451 INFO L878 garLoopResultBuilder]: At program point L30-1(line 30) the Hoare annotation is: (and (= main_~s~0 (+ main_~t~0 (* main_~a~0 main_~a~0))) (= main_~t~0 (+ (* main_~a~0 2) 1))) [2022-04-08 10:57:04,451 INFO L878 garLoopResultBuilder]: At program point L29-2(lines 29 41) the Hoare annotation is: (and (= main_~s~0 (+ main_~t~0 (* main_~a~0 main_~a~0))) (= main_~t~0 (+ (* main_~a~0 2) 1))) [2022-04-08 10:57:04,451 INFO L878 garLoopResultBuilder]: At program point L29-3(lines 29 41) the Hoare annotation is: (and (= main_~s~0 (+ main_~t~0 (* main_~a~0 main_~a~0))) (= main_~t~0 (+ (* main_~a~0 2) 1))) [2022-04-08 10:57:04,451 INFO L885 garLoopResultBuilder]: At program point mainEXIT(lines 20 48) the Hoare annotation is: true [2022-04-08 10:57:04,451 INFO L885 garLoopResultBuilder]: At program point L45(line 45) the Hoare annotation is: true [2022-04-08 10:57:04,452 INFO L885 garLoopResultBuilder]: At program point mainFINAL(lines 20 48) the Hoare annotation is: true [2022-04-08 10:57:04,452 INFO L878 garLoopResultBuilder]: At program point L44(line 44) the Hoare annotation is: (or (and (= main_~t~0 1) (= main_~s~0 1)) (and (= main_~s~0 (+ main_~t~0 (* main_~a~0 main_~a~0))) (= main_~t~0 (+ (* main_~a~0 2) 1)))) [2022-04-08 10:57:04,452 INFO L878 garLoopResultBuilder]: At program point L43(line 43) the Hoare annotation is: (and (= main_~s~0 (+ main_~t~0 (* main_~a~0 main_~a~0))) (= main_~t~0 (+ (* main_~a~0 2) 1))) [2022-04-08 10:57:04,452 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.initFINAL(line -1) the Hoare annotation is: true [2022-04-08 10:57:04,452 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-08 10:57:04,452 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.initEXIT(line -1) the Hoare annotation is: true [2022-04-08 10:57:04,452 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startEXIT(line -1) the Hoare annotation is: true [2022-04-08 10:57:04,452 INFO L885 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-04-08 10:57:04,452 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-04-08 10:57:04,452 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startFINAL(line -1) the Hoare annotation is: true [2022-04-08 10:57:04,453 INFO L885 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 11 17) the Hoare annotation is: true [2022-04-08 10:57:04,453 INFO L878 garLoopResultBuilder]: At program point L13(lines 13 14) the Hoare annotation is: (= |__VERIFIER_assert_#in~cond| 0) [2022-04-08 10:57:04,453 INFO L878 garLoopResultBuilder]: At program point L12(lines 12 15) the Hoare annotation is: (and (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) (or (= |__VERIFIER_assert_#in~cond| 0) (not (= __VERIFIER_assert_~cond 0)))) [2022-04-08 10:57:04,453 INFO L878 garLoopResultBuilder]: At program point L12-2(lines 11 17) the Hoare annotation is: (and (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) (or (= |__VERIFIER_assert_#in~cond| 0) (not (= __VERIFIER_assert_~cond 0)))) [2022-04-08 10:57:04,453 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertEXIT(lines 11 17) the Hoare annotation is: (and (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) (or (= |__VERIFIER_assert_#in~cond| 0) (not (= __VERIFIER_assert_~cond 0)))) [2022-04-08 10:57:04,453 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 14) the Hoare annotation is: (= |__VERIFIER_assert_#in~cond| 0) [2022-04-08 10:57:04,461 INFO L719 BasicCegarLoop]: Path program histogram: [4, 2, 2, 2, 2] [2022-04-08 10:57:04,462 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-04-08 10:57:04,466 WARN L170 areAnnotationChecker]: reach_errorENTRY has no Hoare annotation [2022-04-08 10:57:04,467 WARN L170 areAnnotationChecker]: assume_abort_if_notENTRY has no Hoare annotation [2022-04-08 10:57:04,468 WARN L170 areAnnotationChecker]: reach_errorFINAL has no Hoare annotation [2022-04-08 10:57:04,468 WARN L170 areAnnotationChecker]: L9 has no Hoare annotation [2022-04-08 10:57:04,468 WARN L170 areAnnotationChecker]: L9 has no Hoare annotation [2022-04-08 10:57:04,470 WARN L170 areAnnotationChecker]: L9-2 has no Hoare annotation [2022-04-08 10:57:04,479 INFO L163 areAnnotationChecker]: CFG has 33 edges. 33 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. 0 times interpolants missing. [2022-04-08 10:57:04,487 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 08.04 10:57:04 BoogieIcfgContainer [2022-04-08 10:57:04,487 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-08 10:57:04,488 INFO L158 Benchmark]: Toolchain (without parser) took 7715.57ms. Allocated memory was 195.0MB in the beginning and 250.6MB in the end (delta: 55.6MB). Free memory was 137.8MB in the beginning and 166.5MB in the end (delta: -28.8MB). Peak memory consumption was 27.5MB. Max. memory is 8.0GB. [2022-04-08 10:57:04,488 INFO L158 Benchmark]: CDTParser took 0.18ms. Allocated memory is still 195.0MB. Free memory is still 153.8MB. There was no memory consumed. Max. memory is 8.0GB. [2022-04-08 10:57:04,488 INFO L158 Benchmark]: CACSL2BoogieTranslator took 311.06ms. Allocated memory was 195.0MB in the beginning and 250.6MB in the end (delta: 55.6MB). Free memory was 137.7MB in the beginning and 221.9MB in the end (delta: -84.2MB). Peak memory consumption was 12.5MB. Max. memory is 8.0GB. [2022-04-08 10:57:04,489 INFO L158 Benchmark]: Boogie Preprocessor took 43.56ms. Allocated memory is still 250.6MB. Free memory was 221.9MB in the beginning and 220.3MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-04-08 10:57:04,489 INFO L158 Benchmark]: RCFGBuilder took 347.79ms. Allocated memory is still 250.6MB. Free memory was 220.3MB in the beginning and 208.8MB in the end (delta: 11.6MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-08 10:57:04,489 INFO L158 Benchmark]: TraceAbstraction took 7006.60ms. Allocated memory is still 250.6MB. Free memory was 208.3MB in the beginning and 166.5MB in the end (delta: 41.7MB). Peak memory consumption was 42.8MB. Max. memory is 8.0GB. [2022-04-08 10:57:04,490 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.18ms. Allocated memory is still 195.0MB. Free memory is still 153.8MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 311.06ms. Allocated memory was 195.0MB in the beginning and 250.6MB in the end (delta: 55.6MB). Free memory was 137.7MB in the beginning and 221.9MB in the end (delta: -84.2MB). Peak memory consumption was 12.5MB. Max. memory is 8.0GB. * Boogie Preprocessor took 43.56ms. Allocated memory is still 250.6MB. Free memory was 221.9MB in the beginning and 220.3MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 347.79ms. Allocated memory is still 250.6MB. Free memory was 220.3MB in the beginning and 208.8MB in the end (delta: 11.6MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * TraceAbstraction took 7006.60ms. Allocated memory is still 250.6MB. Free memory was 208.3MB in the beginning and 166.5MB in the end (delta: 41.7MB). Peak memory consumption was 42.8MB. 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, 32 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 6.9s, OverallIterations: 6, TraceHistogramMax: 5, PathProgramHistogramMax: 4, EmptinessCheckTime: 0.0s, AutomataDifference: 2.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.3s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 82 SdHoareTripleChecker+Valid, 0.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 62 mSDsluCounter, 334 SdHoareTripleChecker+Invalid, 0.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 204 mSDsCounter, 59 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 264 IncrementalHoareTripleChecker+Invalid, 323 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 59 mSolverCounterUnsat, 130 mSDtfsCounter, 264 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 176 GetRequests, 138 SyntacticMatches, 4 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=41occurred in iteration=5, InterpolantAutomatonStates: 30, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 6 MinimizatonAttempts, 3 StatesRemovedByMinimization, 2 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 25 LocationsWithAnnotation, 127 PreInvPairs, 180 NumberOfFragments, 203 HoareAnnotationTreeSize, 127 FomulaSimplifications, 108 FormulaSimplificationTreeSizeReduction, 0.1s HoareSimplificationTime, 25 FomulaSimplificationsInter, 502 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: 29]: Loop Invariant Derived loop invariant: s == t + a * a && t == a * 2 + 1 - ProcedureContractResult [Line: 20]: 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))) && (\old(cond) == 0 || !(cond == 0)) RESULT: Ultimate proved your program to be correct! [2022-04-08 10:57:04,506 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...