/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-fb4f59a-m [2022-04-28 10:59:09,183 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-28 10:59:09,184 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-28 10:59:09,216 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-28 10:59:09,216 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-28 10:59:09,217 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-28 10:59:09,220 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-28 10:59:09,221 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-28 10:59:09,222 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-28 10:59:09,226 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-28 10:59:09,226 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-28 10:59:09,227 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-28 10:59:09,228 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-28 10:59:09,229 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-28 10:59:09,230 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-28 10:59:09,232 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-28 10:59:09,232 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-28 10:59:09,233 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-28 10:59:09,234 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-28 10:59:09,238 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-28 10:59:09,240 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-28 10:59:09,241 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-28 10:59:09,241 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-28 10:59:09,242 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-28 10:59:09,243 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-28 10:59:09,248 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-28 10:59:09,248 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-28 10:59:09,249 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-28 10:59:09,249 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-28 10:59:09,250 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-28 10:59:09,251 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-28 10:59:09,251 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-28 10:59:09,252 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-28 10:59:09,252 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-28 10:59:09,253 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-28 10:59:09,253 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-28 10:59:09,253 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-28 10:59:09,254 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-28 10:59:09,254 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-28 10:59:09,254 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-28 10:59:09,255 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-28 10:59:09,256 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-28 10:59:09,256 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-28 10:59:09,266 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-28 10:59:09,266 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-28 10:59:09,267 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-28 10:59:09,267 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-28 10:59:09,267 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-28 10:59:09,267 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-28 10:59:09,267 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-28 10:59:09,267 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-28 10:59:09,267 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-28 10:59:09,268 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-28 10:59:09,268 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-28 10:59:09,268 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-28 10:59:09,268 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-28 10:59:09,268 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-28 10:59:09,268 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-28 10:59:09,269 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-28 10:59:09,269 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-28 10:59:09,269 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-28 10:59:09,269 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-28 10:59:09,269 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-28 10:59:09,269 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-28 10:59:09,269 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-28 10:59:09,269 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-28 10:59:09,422 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-28 10:59:09,433 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-28 10:59:09,435 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-28 10:59:09,436 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-28 10:59:09,436 INFO L275 PluginConnector]: CDTParser initialized [2022-04-28 10:59:09,437 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-28 10:59:09,469 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/263d8c6f1/aa972151e350474bb33f833dadafe9a2/FLAG87e532308 [2022-04-28 10:59:09,874 INFO L306 CDTParser]: Found 1 translation units. [2022-04-28 10:59:09,874 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench/sqrt1-ll.c [2022-04-28 10:59:09,878 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/263d8c6f1/aa972151e350474bb33f833dadafe9a2/FLAG87e532308 [2022-04-28 10:59:09,886 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/263d8c6f1/aa972151e350474bb33f833dadafe9a2 [2022-04-28 10:59:09,888 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-28 10:59:09,889 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-28 10:59:09,891 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-28 10:59:09,891 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-28 10:59:09,893 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-28 10:59:09,893 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.04 10:59:09" (1/1) ... [2022-04-28 10:59:09,894 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6b98bb0b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 10:59:09, skipping insertion in model container [2022-04-28 10:59:09,894 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.04 10:59:09" (1/1) ... [2022-04-28 10:59:09,898 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-28 10:59:09,906 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-28 10:59:10,025 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-28 10:59:10,034 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-28 10:59:10,039 INFO L203 MainTranslator]: Completed pre-run [2022-04-28 10:59:10,046 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-28 10:59:10,050 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-28 10:59:10,058 INFO L208 MainTranslator]: Completed translation [2022-04-28 10:59:10,059 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 10:59:10 WrapperNode [2022-04-28 10:59:10,059 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-28 10:59:10,059 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-28 10:59:10,059 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-28 10:59:10,060 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-28 10:59:10,066 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 10:59:10" (1/1) ... [2022-04-28 10:59:10,066 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 10:59:10" (1/1) ... [2022-04-28 10:59:10,069 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 10:59:10" (1/1) ... [2022-04-28 10:59:10,069 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 10:59:10" (1/1) ... [2022-04-28 10:59:10,073 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 10:59:10" (1/1) ... [2022-04-28 10:59:10,075 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 10:59:10" (1/1) ... [2022-04-28 10:59:10,075 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 10:59:10" (1/1) ... [2022-04-28 10:59:10,076 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-28 10:59:10,077 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-28 10:59:10,077 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-28 10:59:10,077 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-28 10:59:10,078 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 10:59:10" (1/1) ... [2022-04-28 10:59:10,082 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-28 10:59:10,088 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 10:59:10,108 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-28 10:59:10,131 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-28 10:59:10,140 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-28 10:59:10,140 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-28 10:59:10,140 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-28 10:59:10,140 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-28 10:59:10,141 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-28 10:59:10,141 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-28 10:59:10,141 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-28 10:59:10,141 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-28 10:59:10,141 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-28 10:59:10,141 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-28 10:59:10,141 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-28 10:59:10,141 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-28 10:59:10,142 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-28 10:59:10,142 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-28 10:59:10,142 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-28 10:59:10,143 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-28 10:59:10,143 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-28 10:59:10,144 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-28 10:59:10,144 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-28 10:59:10,144 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-28 10:59:10,184 INFO L234 CfgBuilder]: Building ICFG [2022-04-28 10:59:10,185 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-28 10:59:10,268 INFO L275 CfgBuilder]: Performing block encoding [2022-04-28 10:59:10,273 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-28 10:59:10,273 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-28 10:59:10,274 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.04 10:59:10 BoogieIcfgContainer [2022-04-28 10:59:10,274 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-28 10:59:10,275 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-28 10:59:10,275 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-28 10:59:10,277 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-28 10:59:10,277 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 28.04 10:59:09" (1/3) ... [2022-04-28 10:59:10,278 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@744fda98 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.04 10:59:10, skipping insertion in model container [2022-04-28 10:59:10,278 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 10:59:10" (2/3) ... [2022-04-28 10:59:10,278 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@744fda98 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.04 10:59:10, skipping insertion in model container [2022-04-28 10:59:10,278 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.04 10:59:10" (3/3) ... [2022-04-28 10:59:10,279 INFO L111 eAbstractionObserver]: Analyzing ICFG sqrt1-ll.c [2022-04-28 10:59:10,287 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-28 10:59:10,287 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-28 10:59:10,312 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-28 10:59:10,316 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@3b2c8570, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@357d52e3 [2022-04-28 10:59:10,316 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-28 10:59:10,322 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-28 10:59:10,326 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-04-28 10:59:10,326 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 10:59:10,326 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 10:59:10,326 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 10:59:10,329 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 10:59:10,329 INFO L85 PathProgramCache]: Analyzing trace with hash 515438393, now seen corresponding path program 1 times [2022-04-28 10:59:10,334 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 10:59:10,334 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1359885264] [2022-04-28 10:59:10,341 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 10:59:10,341 INFO L85 PathProgramCache]: Analyzing trace with hash 515438393, now seen corresponding path program 2 times [2022-04-28 10:59:10,343 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 10:59:10,343 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1743247397] [2022-04-28 10:59:10,343 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 10:59:10,344 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 10:59:10,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 10:59:10,495 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-28 10:59:10,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 10:59:10,517 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-28 10:59:10,518 INFO L290 TraceCheckUtils]: 1: Hoare triple {28#true} assume true; {28#true} is VALID [2022-04-28 10:59:10,518 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {28#true} {28#true} #65#return; {28#true} is VALID [2022-04-28 10:59:10,521 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-28 10:59:10,521 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-28 10:59:10,521 INFO L290 TraceCheckUtils]: 2: Hoare triple {28#true} assume true; {28#true} is VALID [2022-04-28 10:59:10,522 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {28#true} {28#true} #65#return; {28#true} is VALID [2022-04-28 10:59:10,522 INFO L272 TraceCheckUtils]: 4: Hoare triple {28#true} call #t~ret5 := main(); {28#true} is VALID [2022-04-28 10:59:10,522 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-28 10:59:10,524 INFO L290 TraceCheckUtils]: 6: Hoare triple {28#true} assume false; {29#false} is VALID [2022-04-28 10:59:10,524 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-28 10:59:10,524 INFO L290 TraceCheckUtils]: 8: Hoare triple {29#false} ~cond := #in~cond; {29#false} is VALID [2022-04-28 10:59:10,524 INFO L290 TraceCheckUtils]: 9: Hoare triple {29#false} assume 0 == ~cond; {29#false} is VALID [2022-04-28 10:59:10,525 INFO L290 TraceCheckUtils]: 10: Hoare triple {29#false} assume !false; {29#false} is VALID [2022-04-28 10:59:10,525 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-28 10:59:10,526 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 10:59:10,526 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1743247397] [2022-04-28 10:59:10,527 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1743247397] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 10:59:10,527 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 10:59:10,527 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-28 10:59:10,530 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 10:59:10,531 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1359885264] [2022-04-28 10:59:10,531 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1359885264] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 10:59:10,532 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 10:59:10,532 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-28 10:59:10,532 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [490830563] [2022-04-28 10:59:10,533 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 10:59:10,536 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-28 10:59:10,538 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 10:59:10,540 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-28 10:59:10,557 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-28 10:59:10,557 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-28 10:59:10,557 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 10:59:10,579 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-28 10:59:10,580 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-28 10:59:10,582 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-28 10:59:10,714 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:10,714 INFO L93 Difference]: Finished difference Result 44 states and 66 transitions. [2022-04-28 10:59:10,714 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-28 10:59:10,715 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-28 10:59:10,715 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 10:59:10,716 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-28 10:59:10,721 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 66 transitions. [2022-04-28 10:59:10,721 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-28 10:59:10,725 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 66 transitions. [2022-04-28 10:59:10,725 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 66 transitions. [2022-04-28 10:59:10,799 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 66 edges. 66 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 10:59:10,806 INFO L225 Difference]: With dead ends: 44 [2022-04-28 10:59:10,806 INFO L226 Difference]: Without dead ends: 20 [2022-04-28 10:59:10,808 INFO L412 NwaCegarLoop]: 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-28 10:59:10,810 INFO L413 NwaCegarLoop]: 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-28 10:59:10,810 INFO L414 NwaCegarLoop]: 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-28 10:59:10,820 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2022-04-28 10:59:10,830 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2022-04-28 10:59:10,830 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 10:59:10,830 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-28 10:59:10,831 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-28 10:59:10,831 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-28 10:59:10,834 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:10,834 INFO L93 Difference]: Finished difference Result 20 states and 25 transitions. [2022-04-28 10:59:10,834 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 25 transitions. [2022-04-28 10:59:10,835 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 10:59:10,835 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 10:59:10,835 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-28 10:59:10,835 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-28 10:59:10,837 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:10,838 INFO L93 Difference]: Finished difference Result 20 states and 25 transitions. [2022-04-28 10:59:10,838 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 25 transitions. [2022-04-28 10:59:10,838 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 10:59:10,838 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 10:59:10,838 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 10:59:10,838 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 10:59:10,839 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-28 10:59:10,840 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 25 transitions. [2022-04-28 10:59:10,841 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 25 transitions. Word has length 11 [2022-04-28 10:59:10,841 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 10:59:10,842 INFO L495 AbstractCegarLoop]: Abstraction has 20 states and 25 transitions. [2022-04-28 10:59:10,842 INFO L496 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-28 10:59:10,842 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 20 states and 25 transitions. [2022-04-28 10:59:10,870 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 25 edges. 25 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 10:59:10,871 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 25 transitions. [2022-04-28 10:59:10,871 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-04-28 10:59:10,871 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 10:59:10,871 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 10:59:10,871 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-28 10:59:10,871 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 10:59:10,872 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 10:59:10,872 INFO L85 PathProgramCache]: Analyzing trace with hash 517106689, now seen corresponding path program 1 times [2022-04-28 10:59:10,872 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 10:59:10,872 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1445046905] [2022-04-28 10:59:10,873 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 10:59:10,873 INFO L85 PathProgramCache]: Analyzing trace with hash 517106689, now seen corresponding path program 2 times [2022-04-28 10:59:10,873 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 10:59:10,873 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1755841189] [2022-04-28 10:59:10,874 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 10:59:10,874 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 10:59:10,888 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 10:59:10,959 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-28 10:59:10,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 10:59:10,971 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-28 10:59:10,972 INFO L290 TraceCheckUtils]: 1: Hoare triple {204#true} assume true; {204#true} is VALID [2022-04-28 10:59:10,972 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {204#true} {204#true} #65#return; {204#true} is VALID [2022-04-28 10:59:10,972 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-28 10:59:10,973 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-28 10:59:10,973 INFO L290 TraceCheckUtils]: 2: Hoare triple {204#true} assume true; {204#true} is VALID [2022-04-28 10:59:10,973 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {204#true} {204#true} #65#return; {204#true} is VALID [2022-04-28 10:59:10,973 INFO L272 TraceCheckUtils]: 4: Hoare triple {204#true} call #t~ret5 := main(); {204#true} is VALID [2022-04-28 10:59:10,974 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-28 10:59:10,974 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-28 10:59:10,975 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-28 10:59:10,976 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-28 10:59:10,976 INFO L290 TraceCheckUtils]: 9: Hoare triple {211#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {205#false} is VALID [2022-04-28 10:59:10,976 INFO L290 TraceCheckUtils]: 10: Hoare triple {205#false} assume !false; {205#false} is VALID [2022-04-28 10:59:10,976 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-28 10:59:10,976 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 10:59:10,977 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1755841189] [2022-04-28 10:59:10,977 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1755841189] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 10:59:10,977 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 10:59:10,977 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-28 10:59:10,977 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 10:59:10,977 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1445046905] [2022-04-28 10:59:10,977 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1445046905] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 10:59:10,977 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 10:59:10,978 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-28 10:59:10,978 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2104632312] [2022-04-28 10:59:10,978 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 10:59:10,978 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-28 10:59:10,979 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 10:59:10,979 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-28 10:59:10,987 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-28 10:59:10,987 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-28 10:59:10,987 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 10:59:10,988 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-28 10:59:10,988 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-28 10:59:10,988 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-28 10:59:11,283 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:11,283 INFO L93 Difference]: Finished difference Result 34 states and 44 transitions. [2022-04-28 10:59:11,283 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-28 10:59:11,283 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-28 10:59:11,284 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 10:59:11,284 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-28 10:59:11,289 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 44 transitions. [2022-04-28 10:59:11,289 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-28 10:59:11,295 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 44 transitions. [2022-04-28 10:59:11,296 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 7 states and 44 transitions. [2022-04-28 10:59:11,342 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-28 10:59:11,345 INFO L225 Difference]: With dead ends: 34 [2022-04-28 10:59:11,345 INFO L226 Difference]: Without dead ends: 32 [2022-04-28 10:59:11,345 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-28 10:59:11,348 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 21 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s 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.1s IncrementalHoareTripleChecker+Time [2022-04-28 10:59:11,349 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 34 Invalid, 107 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 81 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-28 10:59:11,351 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-28 10:59:11,366 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 30. [2022-04-28 10:59:11,366 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 10:59:11,367 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-28 10:59:11,368 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-28 10:59:11,368 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-28 10:59:11,373 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:11,373 INFO L93 Difference]: Finished difference Result 32 states and 42 transitions. [2022-04-28 10:59:11,373 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-04-28 10:59:11,374 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 10:59:11,374 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 10:59:11,375 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-28 10:59:11,376 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-28 10:59:11,381 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:11,381 INFO L93 Difference]: Finished difference Result 32 states and 42 transitions. [2022-04-28 10:59:11,381 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-04-28 10:59:11,385 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 10:59:11,385 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 10:59:11,385 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 10:59:11,385 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 10:59:11,386 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-28 10:59:11,387 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 39 transitions. [2022-04-28 10:59:11,387 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 39 transitions. Word has length 11 [2022-04-28 10:59:11,387 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 10:59:11,387 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 39 transitions. [2022-04-28 10:59:11,387 INFO L496 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-28 10:59:11,388 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 30 states and 39 transitions. [2022-04-28 10:59:11,424 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 39 edges. 39 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 10:59:11,425 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 39 transitions. [2022-04-28 10:59:11,425 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2022-04-28 10:59:11,425 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 10:59:11,425 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 10:59:11,425 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-28 10:59:11,426 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 10:59:11,426 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 10:59:11,426 INFO L85 PathProgramCache]: Analyzing trace with hash -1248765655, now seen corresponding path program 1 times [2022-04-28 10:59:11,426 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 10:59:11,426 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1016910074] [2022-04-28 10:59:11,427 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 10:59:11,427 INFO L85 PathProgramCache]: Analyzing trace with hash -1248765655, now seen corresponding path program 2 times [2022-04-28 10:59:11,427 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 10:59:11,427 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1442713798] [2022-04-28 10:59:11,428 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 10:59:11,428 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 10:59:11,437 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 10:59:11,437 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [987681229] [2022-04-28 10:59:11,437 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 10:59:11,437 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 10:59:11,438 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 10:59:11,439 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-28 10:59:11,467 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-28 10:59:11,486 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-28 10:59:11,486 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-28 10:59:11,487 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-28 10:59:11,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 10:59:11,504 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 10:59:11,621 INFO L272 TraceCheckUtils]: 0: Hoare triple {415#true} call ULTIMATE.init(); {415#true} is VALID [2022-04-28 10:59:11,621 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-28 10:59:11,621 INFO L290 TraceCheckUtils]: 2: Hoare triple {415#true} assume true; {415#true} is VALID [2022-04-28 10:59:11,621 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {415#true} {415#true} #65#return; {415#true} is VALID [2022-04-28 10:59:11,621 INFO L272 TraceCheckUtils]: 4: Hoare triple {415#true} call #t~ret5 := main(); {415#true} is VALID [2022-04-28 10:59:11,622 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-28 10:59:11,622 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-28 10:59:11,622 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-28 10:59:11,623 INFO L290 TraceCheckUtils]: 8: Hoare triple {415#true} ~cond := #in~cond; {415#true} is VALID [2022-04-28 10:59:11,623 INFO L290 TraceCheckUtils]: 9: Hoare triple {415#true} assume !(0 == ~cond); {415#true} is VALID [2022-04-28 10:59:11,623 INFO L290 TraceCheckUtils]: 10: Hoare triple {415#true} assume true; {415#true} is VALID [2022-04-28 10:59:11,624 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-28 10:59:11,624 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-28 10:59:11,625 INFO L290 TraceCheckUtils]: 13: Hoare triple {457#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {461#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 10:59:11,625 INFO L290 TraceCheckUtils]: 14: Hoare triple {461#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {416#false} is VALID [2022-04-28 10:59:11,625 INFO L290 TraceCheckUtils]: 15: Hoare triple {416#false} assume !false; {416#false} is VALID [2022-04-28 10:59:11,626 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-28 10:59:11,626 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-28 10:59:11,626 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 10:59:11,626 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1442713798] [2022-04-28 10:59:11,626 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 10:59:11,626 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [987681229] [2022-04-28 10:59:11,626 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [987681229] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 10:59:11,626 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 10:59:11,627 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 10:59:11,627 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 10:59:11,627 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1016910074] [2022-04-28 10:59:11,627 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1016910074] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 10:59:11,627 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 10:59:11,627 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 10:59:11,627 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1034874283] [2022-04-28 10:59:11,627 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 10:59:11,628 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-28 10:59:11,628 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 10:59:11,628 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-28 10:59:11,656 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-28 10:59:11,656 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 10:59:11,656 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 10:59:11,657 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 10:59:11,657 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-28 10:59:11,657 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-28 10:59:11,780 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:11,781 INFO L93 Difference]: Finished difference Result 38 states and 47 transitions. [2022-04-28 10:59:11,781 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-28 10:59:11,781 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-28 10:59:11,781 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 10:59:11,781 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-28 10:59:11,783 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 44 transitions. [2022-04-28 10:59:11,783 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-28 10:59:11,785 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 44 transitions. [2022-04-28 10:59:11,785 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 44 transitions. [2022-04-28 10:59:11,825 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-28 10:59:11,830 INFO L225 Difference]: With dead ends: 38 [2022-04-28 10:59:11,830 INFO L226 Difference]: Without dead ends: 36 [2022-04-28 10:59:11,830 INFO L412 NwaCegarLoop]: 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-28 10:59:11,835 INFO L413 NwaCegarLoop]: 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-28 10:59:11,839 INFO L414 NwaCegarLoop]: 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-28 10:59:11,840 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-04-28 10:59:11,847 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 35. [2022-04-28 10:59:11,848 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 10:59:11,848 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-28 10:59:11,848 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-28 10:59:11,848 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-28 10:59:11,850 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:11,850 INFO L93 Difference]: Finished difference Result 36 states and 45 transitions. [2022-04-28 10:59:11,850 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 45 transitions. [2022-04-28 10:59:11,851 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 10:59:11,851 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 10:59:11,851 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-28 10:59:11,851 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-28 10:59:11,853 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:11,853 INFO L93 Difference]: Finished difference Result 36 states and 45 transitions. [2022-04-28 10:59:11,853 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 45 transitions. [2022-04-28 10:59:11,854 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 10:59:11,854 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 10:59:11,854 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 10:59:11,854 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 10:59:11,855 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-28 10:59:11,860 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 44 transitions. [2022-04-28 10:59:11,860 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 44 transitions. Word has length 16 [2022-04-28 10:59:11,860 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 10:59:11,860 INFO L495 AbstractCegarLoop]: Abstraction has 35 states and 44 transitions. [2022-04-28 10:59:11,860 INFO L496 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-28 10:59:11,860 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 35 states and 44 transitions. [2022-04-28 10:59:11,901 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-28 10:59:11,901 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 44 transitions. [2022-04-28 10:59:11,902 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-04-28 10:59:11,902 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 10:59:11,902 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 10:59:11,920 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-04-28 10:59:12,115 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 10:59:12,116 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 10:59:12,116 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 10:59:12,116 INFO L85 PathProgramCache]: Analyzing trace with hash 1451064513, now seen corresponding path program 1 times [2022-04-28 10:59:12,116 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 10:59:12,116 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1390525474] [2022-04-28 10:59:12,117 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 10:59:12,117 INFO L85 PathProgramCache]: Analyzing trace with hash 1451064513, now seen corresponding path program 2 times [2022-04-28 10:59:12,117 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 10:59:12,117 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [317467914] [2022-04-28 10:59:12,117 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 10:59:12,117 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 10:59:12,133 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 10:59:12,133 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1742644416] [2022-04-28 10:59:12,133 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 10:59:12,134 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 10:59:12,134 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 10:59:12,140 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-28 10:59:12,140 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-28 10:59:12,175 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-28 10:59:12,176 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-28 10:59:12,176 INFO L263 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-28 10:59:12,195 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 10:59:12,196 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 10:59:12,309 INFO L272 TraceCheckUtils]: 0: Hoare triple {687#true} call ULTIMATE.init(); {687#true} is VALID [2022-04-28 10:59:12,310 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-28 10:59:12,310 INFO L290 TraceCheckUtils]: 2: Hoare triple {687#true} assume true; {687#true} is VALID [2022-04-28 10:59:12,310 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {687#true} {687#true} #65#return; {687#true} is VALID [2022-04-28 10:59:12,310 INFO L272 TraceCheckUtils]: 4: Hoare triple {687#true} call #t~ret5 := main(); {687#true} is VALID [2022-04-28 10:59:12,311 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-28 10:59:12,314 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-28 10:59:12,314 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-28 10:59:12,315 INFO L290 TraceCheckUtils]: 8: Hoare triple {687#true} ~cond := #in~cond; {687#true} is VALID [2022-04-28 10:59:12,315 INFO L290 TraceCheckUtils]: 9: Hoare triple {687#true} assume !(0 == ~cond); {687#true} is VALID [2022-04-28 10:59:12,315 INFO L290 TraceCheckUtils]: 10: Hoare triple {687#true} assume true; {687#true} is VALID [2022-04-28 10:59:12,316 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-28 10:59:12,316 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-28 10:59:12,316 INFO L290 TraceCheckUtils]: 13: Hoare triple {687#true} ~cond := #in~cond; {687#true} is VALID [2022-04-28 10:59:12,316 INFO L290 TraceCheckUtils]: 14: Hoare triple {687#true} assume !(0 == ~cond); {687#true} is VALID [2022-04-28 10:59:12,316 INFO L290 TraceCheckUtils]: 15: Hoare triple {687#true} assume true; {687#true} is VALID [2022-04-28 10:59:12,320 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-28 10:59:12,323 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-28 10:59:12,324 INFO L290 TraceCheckUtils]: 18: Hoare triple {744#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {748#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 10:59:12,324 INFO L290 TraceCheckUtils]: 19: Hoare triple {748#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {688#false} is VALID [2022-04-28 10:59:12,324 INFO L290 TraceCheckUtils]: 20: Hoare triple {688#false} assume !false; {688#false} is VALID [2022-04-28 10:59:12,324 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-28 10:59:12,324 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-28 10:59:12,324 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 10:59:12,325 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [317467914] [2022-04-28 10:59:12,325 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 10:59:12,325 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1742644416] [2022-04-28 10:59:12,325 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1742644416] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 10:59:12,325 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 10:59:12,325 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 10:59:12,325 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 10:59:12,325 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1390525474] [2022-04-28 10:59:12,325 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1390525474] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 10:59:12,325 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 10:59:12,325 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 10:59:12,326 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [392647775] [2022-04-28 10:59:12,326 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 10:59:12,326 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-28 10:59:12,326 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 10:59:12,326 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-28 10:59:12,338 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-28 10:59:12,338 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 10:59:12,339 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 10:59:12,339 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 10:59:12,339 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-28 10:59:12,339 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-28 10:59:12,456 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:12,457 INFO L93 Difference]: Finished difference Result 42 states and 50 transitions. [2022-04-28 10:59:12,457 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-28 10:59:12,457 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-28 10:59:12,457 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 10:59:12,457 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-28 10:59:12,458 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 44 transitions. [2022-04-28 10:59:12,458 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-28 10:59:12,459 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 44 transitions. [2022-04-28 10:59:12,459 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 44 transitions. [2022-04-28 10:59:12,492 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-28 10:59:12,493 INFO L225 Difference]: With dead ends: 42 [2022-04-28 10:59:12,493 INFO L226 Difference]: Without dead ends: 37 [2022-04-28 10:59:12,494 INFO L412 NwaCegarLoop]: 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-28 10:59:12,494 INFO L413 NwaCegarLoop]: 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-28 10:59:12,494 INFO L414 NwaCegarLoop]: 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-28 10:59:12,495 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2022-04-28 10:59:12,507 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2022-04-28 10:59:12,507 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 10:59:12,508 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-28 10:59:12,508 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-28 10:59:12,508 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-28 10:59:12,509 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:12,510 INFO L93 Difference]: Finished difference Result 37 states and 42 transitions. [2022-04-28 10:59:12,510 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 42 transitions. [2022-04-28 10:59:12,510 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 10:59:12,510 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 10:59:12,510 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-28 10:59:12,510 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-28 10:59:12,512 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:12,512 INFO L93 Difference]: Finished difference Result 37 states and 42 transitions. [2022-04-28 10:59:12,512 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 42 transitions. [2022-04-28 10:59:12,512 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 10:59:12,512 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 10:59:12,512 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 10:59:12,512 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 10:59:12,513 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-28 10:59:12,514 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 42 transitions. [2022-04-28 10:59:12,514 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 42 transitions. Word has length 21 [2022-04-28 10:59:12,514 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 10:59:12,514 INFO L495 AbstractCegarLoop]: Abstraction has 37 states and 42 transitions. [2022-04-28 10:59:12,514 INFO L496 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-28 10:59:12,515 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 37 states and 42 transitions. [2022-04-28 10:59:12,564 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-28 10:59:12,565 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 42 transitions. [2022-04-28 10:59:12,565 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-28 10:59:12,565 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 10:59:12,566 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 10:59:12,581 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-28 10:59:12,781 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2022-04-28 10:59:12,782 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 10:59:12,782 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 10:59:12,782 INFO L85 PathProgramCache]: Analyzing trace with hash 412610311, now seen corresponding path program 1 times [2022-04-28 10:59:12,782 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 10:59:12,782 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1097642063] [2022-04-28 10:59:12,975 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-28 10:59:12,976 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-28 10:59:12,976 INFO L85 PathProgramCache]: Analyzing trace with hash 412610311, now seen corresponding path program 2 times [2022-04-28 10:59:12,976 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 10:59:12,976 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1736615929] [2022-04-28 10:59:12,976 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 10:59:12,976 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 10:59:12,984 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 10:59:12,984 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2136821045] [2022-04-28 10:59:12,984 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 10:59:12,985 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 10:59:12,985 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 10:59:12,994 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-28 10:59:12,996 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-28 10:59:13,026 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-28 10:59:13,026 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-28 10:59:13,027 INFO L263 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-28 10:59:13,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 10:59:13,034 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 10:59:13,149 INFO L272 TraceCheckUtils]: 0: Hoare triple {988#true} call ULTIMATE.init(); {988#true} is VALID [2022-04-28 10:59:13,149 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-28 10:59:13,150 INFO L290 TraceCheckUtils]: 2: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-28 10:59:13,150 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {988#true} {988#true} #65#return; {988#true} is VALID [2022-04-28 10:59:13,150 INFO L272 TraceCheckUtils]: 4: Hoare triple {988#true} call #t~ret5 := main(); {988#true} is VALID [2022-04-28 10:59:13,150 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-28 10:59:13,151 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-28 10:59:13,151 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-28 10:59:13,151 INFO L290 TraceCheckUtils]: 8: Hoare triple {988#true} ~cond := #in~cond; {988#true} is VALID [2022-04-28 10:59:13,151 INFO L290 TraceCheckUtils]: 9: Hoare triple {988#true} assume !(0 == ~cond); {988#true} is VALID [2022-04-28 10:59:13,151 INFO L290 TraceCheckUtils]: 10: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-28 10:59:13,152 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-28 10:59:13,152 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-28 10:59:13,152 INFO L290 TraceCheckUtils]: 13: Hoare triple {988#true} ~cond := #in~cond; {988#true} is VALID [2022-04-28 10:59:13,152 INFO L290 TraceCheckUtils]: 14: Hoare triple {988#true} assume !(0 == ~cond); {988#true} is VALID [2022-04-28 10:59:13,153 INFO L290 TraceCheckUtils]: 15: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-28 10:59:13,153 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-28 10:59:13,153 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-28 10:59:13,153 INFO L290 TraceCheckUtils]: 18: Hoare triple {988#true} ~cond := #in~cond; {988#true} is VALID [2022-04-28 10:59:13,154 INFO L290 TraceCheckUtils]: 19: Hoare triple {988#true} assume !(0 == ~cond); {988#true} is VALID [2022-04-28 10:59:13,154 INFO L290 TraceCheckUtils]: 20: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-28 10:59:13,154 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-28 10:59:13,155 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-28 10:59:13,155 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-28 10:59:13,156 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-28 10:59:13,156 INFO L290 TraceCheckUtils]: 25: Hoare triple {1067#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1071#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 10:59:13,157 INFO L290 TraceCheckUtils]: 26: Hoare triple {1071#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {989#false} is VALID [2022-04-28 10:59:13,157 INFO L290 TraceCheckUtils]: 27: Hoare triple {989#false} assume !false; {989#false} is VALID [2022-04-28 10:59:13,158 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-28 10:59:13,158 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-28 10:59:13,269 INFO L290 TraceCheckUtils]: 27: Hoare triple {989#false} assume !false; {989#false} is VALID [2022-04-28 10:59:13,270 INFO L290 TraceCheckUtils]: 26: Hoare triple {1071#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {989#false} is VALID [2022-04-28 10:59:13,270 INFO L290 TraceCheckUtils]: 25: Hoare triple {1067#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1071#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 10:59:13,271 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-28 10:59:13,271 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-28 10:59:13,272 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-28 10:59:13,273 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-28 10:59:13,273 INFO L290 TraceCheckUtils]: 20: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-28 10:59:13,273 INFO L290 TraceCheckUtils]: 19: Hoare triple {988#true} assume !(0 == ~cond); {988#true} is VALID [2022-04-28 10:59:13,273 INFO L290 TraceCheckUtils]: 18: Hoare triple {988#true} ~cond := #in~cond; {988#true} is VALID [2022-04-28 10:59:13,273 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-28 10:59:13,275 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-28 10:59:13,275 INFO L290 TraceCheckUtils]: 15: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-28 10:59:13,275 INFO L290 TraceCheckUtils]: 14: Hoare triple {988#true} assume !(0 == ~cond); {988#true} is VALID [2022-04-28 10:59:13,275 INFO L290 TraceCheckUtils]: 13: Hoare triple {988#true} ~cond := #in~cond; {988#true} is VALID [2022-04-28 10:59:13,275 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-28 10:59:13,276 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-28 10:59:13,276 INFO L290 TraceCheckUtils]: 10: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-28 10:59:13,276 INFO L290 TraceCheckUtils]: 9: Hoare triple {988#true} assume !(0 == ~cond); {988#true} is VALID [2022-04-28 10:59:13,276 INFO L290 TraceCheckUtils]: 8: Hoare triple {988#true} ~cond := #in~cond; {988#true} is VALID [2022-04-28 10:59:13,276 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-28 10:59:13,277 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-28 10:59:13,278 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-28 10:59:13,278 INFO L272 TraceCheckUtils]: 4: Hoare triple {988#true} call #t~ret5 := main(); {988#true} is VALID [2022-04-28 10:59:13,278 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {988#true} {988#true} #65#return; {988#true} is VALID [2022-04-28 10:59:13,278 INFO L290 TraceCheckUtils]: 2: Hoare triple {988#true} assume true; {988#true} is VALID [2022-04-28 10:59:13,278 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-28 10:59:13,278 INFO L272 TraceCheckUtils]: 0: Hoare triple {988#true} call ULTIMATE.init(); {988#true} is VALID [2022-04-28 10:59:13,279 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-28 10:59:13,279 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 10:59:13,279 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1736615929] [2022-04-28 10:59:13,279 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 10:59:13,279 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2136821045] [2022-04-28 10:59:13,279 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2136821045] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-28 10:59:13,279 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-28 10:59:13,279 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-28 10:59:13,279 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 10:59:13,280 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1097642063] [2022-04-28 10:59:13,280 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1097642063] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 10:59:13,280 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 10:59:13,280 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 10:59:13,280 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [536468633] [2022-04-28 10:59:13,280 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 10:59:13,280 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-28 10:59:13,280 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 10:59:13,281 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-28 10:59:13,299 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-28 10:59:13,299 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 10:59:13,299 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 10:59:13,299 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 10:59:13,300 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-28 10:59:13,300 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-28 10:59:13,403 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:13,403 INFO L93 Difference]: Finished difference Result 43 states and 47 transitions. [2022-04-28 10:59:13,403 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-28 10:59:13,403 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-28 10:59:13,403 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 10:59:13,403 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-28 10:59:13,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 30 transitions. [2022-04-28 10:59:13,404 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-28 10:59:13,405 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 30 transitions. [2022-04-28 10:59:13,405 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 30 transitions. [2022-04-28 10:59:13,429 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 30 edges. 30 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 10:59:13,430 INFO L225 Difference]: With dead ends: 43 [2022-04-28 10:59:13,430 INFO L226 Difference]: Without dead ends: 41 [2022-04-28 10:59:13,431 INFO L412 NwaCegarLoop]: 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-28 10:59:13,431 INFO L413 NwaCegarLoop]: 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-28 10:59:13,431 INFO L414 NwaCegarLoop]: 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-28 10:59:13,432 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-04-28 10:59:13,450 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-04-28 10:59:13,450 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 10:59:13,450 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-28 10:59:13,450 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-28 10:59:13,450 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-28 10:59:13,452 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:13,452 INFO L93 Difference]: Finished difference Result 41 states and 45 transitions. [2022-04-28 10:59:13,452 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-28 10:59:13,452 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 10:59:13,452 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 10:59:13,452 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-28 10:59:13,452 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-28 10:59:13,453 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:13,454 INFO L93 Difference]: Finished difference Result 41 states and 45 transitions. [2022-04-28 10:59:13,454 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-28 10:59:13,454 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 10:59:13,454 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 10:59:13,454 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 10:59:13,454 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 10:59:13,454 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-28 10:59:13,455 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 45 transitions. [2022-04-28 10:59:13,455 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 45 transitions. Word has length 28 [2022-04-28 10:59:13,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 10:59:13,455 INFO L495 AbstractCegarLoop]: Abstraction has 41 states and 45 transitions. [2022-04-28 10:59:13,456 INFO L496 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-28 10:59:13,456 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 41 states and 45 transitions. [2022-04-28 10:59:13,495 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-28 10:59:13,496 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-28 10:59:13,496 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-04-28 10:59:13,496 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 10:59:13,496 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 10:59:13,524 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-28 10:59:13,712 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 10:59:13,712 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 10:59:13,713 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 10:59:13,713 INFO L85 PathProgramCache]: Analyzing trace with hash -1543321117, now seen corresponding path program 3 times [2022-04-28 10:59:13,713 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 10:59:13,713 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [301924175] [2022-04-28 10:59:13,904 INFO L97 AcceleratorQvasr]: Qvasr could not accelerate loop because java.lang.UnsupportedOperationException: Cannot deal with arrays. [2022-04-28 10:59:13,904 INFO L274 tedInterpolationCore]: Could not compute an accelerate. [2022-04-28 10:59:13,904 INFO L85 PathProgramCache]: Analyzing trace with hash -1543321117, now seen corresponding path program 4 times [2022-04-28 10:59:13,904 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 10:59:13,904 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1092662462] [2022-04-28 10:59:13,904 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 10:59:13,904 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 10:59:13,912 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 10:59:13,912 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [377350394] [2022-04-28 10:59:13,912 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-28 10:59:13,912 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 10:59:13,912 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 10:59:13,913 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-28 10:59:13,914 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-28 10:59:13,949 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-28 10:59:13,949 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-28 10:59:13,950 INFO L263 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 24 conjunts are in the unsatisfiable core [2022-04-28 10:59:14,012 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 10:59:14,014 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 10:59:14,281 INFO L272 TraceCheckUtils]: 0: Hoare triple {1414#true} call ULTIMATE.init(); {1414#true} is VALID [2022-04-28 10:59:14,281 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-28 10:59:14,281 INFO L290 TraceCheckUtils]: 2: Hoare triple {1414#true} assume true; {1414#true} is VALID [2022-04-28 10:59:14,281 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1414#true} {1414#true} #65#return; {1414#true} is VALID [2022-04-28 10:59:14,281 INFO L272 TraceCheckUtils]: 4: Hoare triple {1414#true} call #t~ret5 := main(); {1414#true} is VALID [2022-04-28 10:59:14,282 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-28 10:59:14,282 INFO L290 TraceCheckUtils]: 6: Hoare triple {1414#true} assume !false; {1414#true} is VALID [2022-04-28 10:59:14,282 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-28 10:59:14,282 INFO L290 TraceCheckUtils]: 8: Hoare triple {1414#true} ~cond := #in~cond; {1414#true} is VALID [2022-04-28 10:59:14,282 INFO L290 TraceCheckUtils]: 9: Hoare triple {1414#true} assume !(0 == ~cond); {1414#true} is VALID [2022-04-28 10:59:14,282 INFO L290 TraceCheckUtils]: 10: Hoare triple {1414#true} assume true; {1414#true} is VALID [2022-04-28 10:59:14,282 INFO L284 TraceCheckUtils]: 11: Hoare quadruple {1414#true} {1414#true} #53#return; {1414#true} is VALID [2022-04-28 10:59:14,282 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-28 10:59:14,283 INFO L290 TraceCheckUtils]: 13: Hoare triple {1414#true} ~cond := #in~cond; {1458#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-28 10:59:14,283 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-28 10:59:14,284 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-28 10:59:14,284 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-28 10:59:14,284 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-28 10:59:14,285 INFO L290 TraceCheckUtils]: 18: Hoare triple {1414#true} ~cond := #in~cond; {1458#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-28 10:59:14,285 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-28 10:59:14,285 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-28 10:59:14,286 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-28 10:59:14,289 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-28 10:59:14,290 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-28 10:59:14,290 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-28 10:59:14,290 INFO L290 TraceCheckUtils]: 25: Hoare triple {1414#true} ~cond := #in~cond; {1458#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-28 10:59:14,291 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-28 10:59:14,291 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-28 10:59:14,292 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-28 10:59:14,292 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-28 10:59:14,293 INFO L290 TraceCheckUtils]: 30: Hoare triple {1511#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1515#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 10:59:14,293 INFO L290 TraceCheckUtils]: 31: Hoare triple {1515#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1415#false} is VALID [2022-04-28 10:59:14,293 INFO L290 TraceCheckUtils]: 32: Hoare triple {1415#false} assume !false; {1415#false} is VALID [2022-04-28 10:59:14,293 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-28 10:59:14,293 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-28 10:59:14,711 INFO L290 TraceCheckUtils]: 32: Hoare triple {1415#false} assume !false; {1415#false} is VALID [2022-04-28 10:59:14,712 INFO L290 TraceCheckUtils]: 31: Hoare triple {1515#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1415#false} is VALID [2022-04-28 10:59:14,712 INFO L290 TraceCheckUtils]: 30: Hoare triple {1511#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1515#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 10:59:14,713 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-28 10:59:14,713 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-28 10:59:14,714 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-28 10:59:14,714 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-28 10:59:14,714 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-28 10:59:14,714 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-28 10:59:14,715 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-28 10:59:14,717 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-28 10:59:14,718 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-28 10:59:14,718 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-28 10:59:14,719 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-28 10:59:14,719 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-28 10:59:14,719 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-28 10:59:14,719 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1414#true} {1414#true} #55#return; {1414#true} is VALID [2022-04-28 10:59:14,720 INFO L290 TraceCheckUtils]: 15: Hoare triple {1414#true} assume true; {1414#true} is VALID [2022-04-28 10:59:14,720 INFO L290 TraceCheckUtils]: 14: Hoare triple {1414#true} assume !(0 == ~cond); {1414#true} is VALID [2022-04-28 10:59:14,720 INFO L290 TraceCheckUtils]: 13: Hoare triple {1414#true} ~cond := #in~cond; {1414#true} is VALID [2022-04-28 10:59:14,720 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-28 10:59:14,720 INFO L284 TraceCheckUtils]: 11: Hoare quadruple {1414#true} {1414#true} #53#return; {1414#true} is VALID [2022-04-28 10:59:14,720 INFO L290 TraceCheckUtils]: 10: Hoare triple {1414#true} assume true; {1414#true} is VALID [2022-04-28 10:59:14,720 INFO L290 TraceCheckUtils]: 9: Hoare triple {1414#true} assume !(0 == ~cond); {1414#true} is VALID [2022-04-28 10:59:14,720 INFO L290 TraceCheckUtils]: 8: Hoare triple {1414#true} ~cond := #in~cond; {1414#true} is VALID [2022-04-28 10:59:14,720 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-28 10:59:14,720 INFO L290 TraceCheckUtils]: 6: Hoare triple {1414#true} assume !false; {1414#true} is VALID [2022-04-28 10:59:14,721 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-28 10:59:14,721 INFO L272 TraceCheckUtils]: 4: Hoare triple {1414#true} call #t~ret5 := main(); {1414#true} is VALID [2022-04-28 10:59:14,721 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1414#true} {1414#true} #65#return; {1414#true} is VALID [2022-04-28 10:59:14,721 INFO L290 TraceCheckUtils]: 2: Hoare triple {1414#true} assume true; {1414#true} is VALID [2022-04-28 10:59:14,721 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-28 10:59:14,721 INFO L272 TraceCheckUtils]: 0: Hoare triple {1414#true} call ULTIMATE.init(); {1414#true} is VALID [2022-04-28 10:59:14,721 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-28 10:59:14,721 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 10:59:14,721 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1092662462] [2022-04-28 10:59:14,721 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 10:59:14,722 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [377350394] [2022-04-28 10:59:14,722 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [377350394] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-28 10:59:14,722 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-28 10:59:14,722 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 11 [2022-04-28 10:59:14,722 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 10:59:14,722 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [301924175] [2022-04-28 10:59:14,722 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [301924175] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 10:59:14,722 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 10:59:14,722 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-28 10:59:14,722 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [769421062] [2022-04-28 10:59:14,722 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 10:59:14,723 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-28 10:59:14,723 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 10:59:14,723 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-28 10:59:14,744 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 27 edges. 27 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 10:59:14,744 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-28 10:59:14,744 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 10:59:14,745 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-28 10:59:14,745 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-04-28 10:59:14,745 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-28 10:59:15,255 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:15,256 INFO L93 Difference]: Finished difference Result 41 states and 45 transitions. [2022-04-28 10:59:15,256 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-28 10:59:15,256 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-28 10:59:15,256 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 10:59:15,256 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-28 10:59:15,257 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 25 transitions. [2022-04-28 10:59:15,257 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-28 10:59:15,258 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 25 transitions. [2022-04-28 10:59:15,258 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 25 transitions. [2022-04-28 10:59:15,283 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 25 edges. 25 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 10:59:15,283 INFO L225 Difference]: With dead ends: 41 [2022-04-28 10:59:15,283 INFO L226 Difference]: Without dead ends: 0 [2022-04-28 10:59:15,284 INFO L412 NwaCegarLoop]: 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-28 10:59:15,284 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 12 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s 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.1s IncrementalHoareTripleChecker+Time [2022-04-28 10:59:15,285 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 54 Invalid, 88 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-28 10:59:15,285 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-28 10:59:15,285 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-28 10:59:15,285 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 10:59:15,285 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-28 10:59:15,285 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-28 10:59:15,285 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-28 10:59:15,285 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:15,285 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-28 10:59:15,285 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-28 10:59:15,285 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 10:59:15,286 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 10:59:15,286 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-28 10:59:15,286 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-28 10:59:15,286 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 10:59:15,286 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-28 10:59:15,286 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-28 10:59:15,286 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 10:59:15,286 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 10:59:15,286 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 10:59:15,286 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 10:59:15,286 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-28 10:59:15,286 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-28 10:59:15,286 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 33 [2022-04-28 10:59:15,286 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 10:59:15,286 INFO L495 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-28 10:59:15,287 INFO L496 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-28 10:59:15,287 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 0 states and 0 transitions. [2022-04-28 10:59:15,287 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-28 10:59:15,287 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-28 10:59:15,287 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 10:59:15,289 INFO L805 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-28 10:59:15,307 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-28 10:59:15,499 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 10:59:15,501 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-04-28 10:59:15,801 INFO L899 garLoopResultBuilder]: For program point reach_errorEXIT(line 5) no Hoare annotation was computed. [2022-04-28 10:59:15,801 INFO L899 garLoopResultBuilder]: For program point reach_errorENTRY(line 5) no Hoare annotation was computed. [2022-04-28 10:59:15,801 INFO L899 garLoopResultBuilder]: For program point reach_errorFINAL(line 5) no Hoare annotation was computed. [2022-04-28 10:59:15,801 INFO L899 garLoopResultBuilder]: For program point assume_abort_if_notENTRY(lines 8 10) no Hoare annotation was computed. [2022-04-28 10:59:15,801 INFO L899 garLoopResultBuilder]: For program point L9(line 9) no Hoare annotation was computed. [2022-04-28 10:59:15,801 INFO L899 garLoopResultBuilder]: For program point L9-2(lines 8 10) no Hoare annotation was computed. [2022-04-28 10:59:15,801 INFO L899 garLoopResultBuilder]: For program point assume_abort_if_notEXIT(lines 8 10) no Hoare annotation was computed. [2022-04-28 10:59:15,801 INFO L895 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-28 10:59:15,801 INFO L895 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-28 10:59:15,802 INFO L895 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-28 10:59:15,802 INFO L902 garLoopResultBuilder]: At program point mainENTRY(lines 20 48) the Hoare annotation is: true [2022-04-28 10:59:15,802 INFO L895 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-28 10:59:15,802 INFO L895 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-28 10:59:15,802 INFO L895 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-28 10:59:15,802 INFO L902 garLoopResultBuilder]: At program point mainEXIT(lines 20 48) the Hoare annotation is: true [2022-04-28 10:59:15,802 INFO L902 garLoopResultBuilder]: At program point L45(line 45) the Hoare annotation is: true [2022-04-28 10:59:15,802 INFO L902 garLoopResultBuilder]: At program point mainFINAL(lines 20 48) the Hoare annotation is: true [2022-04-28 10:59:15,802 INFO L895 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-28 10:59:15,802 INFO L895 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-28 10:59:15,802 INFO L902 garLoopResultBuilder]: At program point ULTIMATE.initFINAL(line -1) the Hoare annotation is: true [2022-04-28 10:59:15,802 INFO L895 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-28 10:59:15,802 INFO L902 garLoopResultBuilder]: At program point ULTIMATE.initEXIT(line -1) the Hoare annotation is: true [2022-04-28 10:59:15,802 INFO L902 garLoopResultBuilder]: At program point ULTIMATE.startEXIT(line -1) the Hoare annotation is: true [2022-04-28 10:59:15,802 INFO L902 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-04-28 10:59:15,802 INFO L902 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-04-28 10:59:15,803 INFO L902 garLoopResultBuilder]: At program point ULTIMATE.startFINAL(line -1) the Hoare annotation is: true [2022-04-28 10:59:15,803 INFO L902 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 11 17) the Hoare annotation is: true [2022-04-28 10:59:15,803 INFO L895 garLoopResultBuilder]: At program point L13(lines 13 14) the Hoare annotation is: (= |__VERIFIER_assert_#in~cond| 0) [2022-04-28 10:59:15,803 INFO L895 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-28 10:59:15,804 INFO L895 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-28 10:59:15,804 INFO L895 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-28 10:59:15,804 INFO L895 garLoopResultBuilder]: At program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 14) the Hoare annotation is: (= |__VERIFIER_assert_#in~cond| 0) [2022-04-28 10:59:15,807 INFO L356 BasicCegarLoop]: Path program histogram: [4, 2, 2, 2, 2] [2022-04-28 10:59:15,808 INFO L176 ceAbstractionStarter]: Computing trace abstraction results [2022-04-28 10:59:15,810 WARN L170 areAnnotationChecker]: reach_errorENTRY has no Hoare annotation [2022-04-28 10:59:15,811 WARN L170 areAnnotationChecker]: assume_abort_if_notENTRY has no Hoare annotation [2022-04-28 10:59:15,812 WARN L170 areAnnotationChecker]: reach_errorFINAL has no Hoare annotation [2022-04-28 10:59:15,812 WARN L170 areAnnotationChecker]: L9 has no Hoare annotation [2022-04-28 10:59:15,812 WARN L170 areAnnotationChecker]: L9 has no Hoare annotation [2022-04-28 10:59:15,814 WARN L170 areAnnotationChecker]: L9-2 has no Hoare annotation [2022-04-28 10:59:15,819 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-28 10:59:15,831 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 28.04 10:59:15 BoogieIcfgContainer [2022-04-28 10:59:15,831 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-28 10:59:15,832 INFO L158 Benchmark]: Toolchain (without parser) took 5943.48ms. Allocated memory was 187.7MB in the beginning and 233.8MB in the end (delta: 46.1MB). Free memory was 138.2MB in the beginning and 207.4MB in the end (delta: -69.2MB). Peak memory consumption was 106.4MB. Max. memory is 8.0GB. [2022-04-28 10:59:15,832 INFO L158 Benchmark]: CDTParser took 0.12ms. Allocated memory is still 187.7MB. Free memory was 154.9MB in the beginning and 154.7MB in the end (delta: 146.9kB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-28 10:59:15,832 INFO L158 Benchmark]: CACSL2BoogieTranslator took 168.16ms. Allocated memory is still 187.7MB. Free memory was 137.9MB in the beginning and 164.6MB in the end (delta: -26.7MB). Peak memory consumption was 8.2MB. Max. memory is 8.0GB. [2022-04-28 10:59:15,833 INFO L158 Benchmark]: Boogie Preprocessor took 17.09ms. Allocated memory is still 187.7MB. Free memory was 164.6MB in the beginning and 163.5MB in the end (delta: 1.0MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-28 10:59:15,833 INFO L158 Benchmark]: RCFGBuilder took 197.15ms. Allocated memory is still 187.7MB. Free memory was 163.5MB in the beginning and 152.5MB in the end (delta: 11.0MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. [2022-04-28 10:59:15,833 INFO L158 Benchmark]: TraceAbstraction took 5556.57ms. Allocated memory was 187.7MB in the beginning and 233.8MB in the end (delta: 46.1MB). Free memory was 152.0MB in the beginning and 207.4MB in the end (delta: -55.4MB). Peak memory consumption was 119.2MB. Max. memory is 8.0GB. [2022-04-28 10:59:15,834 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.12ms. Allocated memory is still 187.7MB. Free memory was 154.9MB in the beginning and 154.7MB in the end (delta: 146.9kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 168.16ms. Allocated memory is still 187.7MB. Free memory was 137.9MB in the beginning and 164.6MB in the end (delta: -26.7MB). Peak memory consumption was 8.2MB. Max. memory is 8.0GB. * Boogie Preprocessor took 17.09ms. Allocated memory is still 187.7MB. Free memory was 164.6MB in the beginning and 163.5MB in the end (delta: 1.0MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 197.15ms. Allocated memory is still 187.7MB. Free memory was 163.5MB in the beginning and 152.5MB in the end (delta: 11.0MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. * TraceAbstraction took 5556.57ms. Allocated memory was 187.7MB in the beginning and 233.8MB in the end (delta: 46.1MB). Free memory was 152.0MB in the beginning and 207.4MB in the end (delta: -55.4MB). Peak memory consumption was 119.2MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 14]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 32 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 5.5s, OverallIterations: 6, TraceHistogramMax: 5, PathProgramHistogramMax: 4, EmptinessCheckTime: 0.0s, AutomataDifference: 1.6s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.3s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 82 SdHoareTripleChecker+Valid, 0.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 62 mSDsluCounter, 334 SdHoareTripleChecker+Invalid, 0.4s 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.2s 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.1s 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-28 10:59:15,849 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...