/usr/bin/java -ea -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound2.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-e106359-m [2022-04-15 13:48:18,487 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-15 13:48:18,489 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-15 13:48:18,527 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-15 13:48:18,528 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-15 13:48:18,529 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-15 13:48:18,531 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-15 13:48:18,535 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-15 13:48:18,537 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-15 13:48:18,540 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-15 13:48:18,541 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-15 13:48:18,542 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-15 13:48:18,542 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-15 13:48:18,545 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-15 13:48:18,546 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-15 13:48:18,548 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-15 13:48:18,549 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-15 13:48:18,549 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-15 13:48:18,551 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-15 13:48:18,555 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-15 13:48:18,557 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-15 13:48:18,558 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-15 13:48:18,558 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-15 13:48:18,559 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-15 13:48:18,560 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-15 13:48:18,565 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-15 13:48:18,565 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-15 13:48:18,565 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-15 13:48:18,566 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-15 13:48:18,566 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-15 13:48:18,567 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-15 13:48:18,568 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-15 13:48:18,569 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-15 13:48:18,569 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-15 13:48:18,570 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-15 13:48:18,570 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-15 13:48:18,570 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-15 13:48:18,571 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-15 13:48:18,571 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-15 13:48:18,571 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-15 13:48:18,571 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-15 13:48:18,573 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-15 13:48:18,573 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-15 13:48:18,582 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-15 13:48:18,582 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-15 13:48:18,584 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-15 13:48:18,584 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-15 13:48:18,584 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-15 13:48:18,584 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-15 13:48:18,584 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-15 13:48:18,584 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-15 13:48:18,584 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-15 13:48:18,585 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-15 13:48:18,585 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-15 13:48:18,585 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-15 13:48:18,585 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-15 13:48:18,585 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-15 13:48:18,585 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-15 13:48:18,585 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 13:48:18,585 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-15 13:48:18,586 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-15 13:48:18,586 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-15 13:48:18,586 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-15 13:48:18,586 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-15 13:48:18,586 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-15 13:48:18,586 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-15 13:48:18,776 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-15 13:48:18,795 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-15 13:48:18,797 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-15 13:48:18,798 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-15 13:48:18,799 INFO L275 PluginConnector]: CDTParser initialized [2022-04-15 13:48:18,800 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound2.c [2022-04-15 13:48:18,845 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b60ce1fc8/66502e2d74244e358b586c6ab82b14b1/FLAG9cab2ba7e [2022-04-15 13:48:19,197 INFO L306 CDTParser]: Found 1 translation units. [2022-04-15 13:48:19,198 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound2.c [2022-04-15 13:48:19,202 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b60ce1fc8/66502e2d74244e358b586c6ab82b14b1/FLAG9cab2ba7e [2022-04-15 13:48:19,210 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b60ce1fc8/66502e2d74244e358b586c6ab82b14b1 [2022-04-15 13:48:19,211 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-15 13:48:19,212 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-15 13:48:19,213 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-15 13:48:19,213 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-15 13:48:19,215 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-15 13:48:19,216 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 01:48:19" (1/1) ... [2022-04-15 13:48:19,217 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@39bf2dc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 01:48:19, skipping insertion in model container [2022-04-15 13:48:19,217 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 01:48:19" (1/1) ... [2022-04-15 13:48:19,221 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-15 13:48:19,230 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-15 13:48:19,353 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound2.c[588,601] [2022-04-15 13:48:19,376 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 13:48:19,382 INFO L203 MainTranslator]: Completed pre-run [2022-04-15 13:48:19,389 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/cohencu-ll_unwindbound2.c[588,601] [2022-04-15 13:48:19,397 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 13:48:19,405 INFO L208 MainTranslator]: Completed translation [2022-04-15 13:48:19,405 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 01:48:19 WrapperNode [2022-04-15 13:48:19,406 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-15 13:48:19,406 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-15 13:48:19,406 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-15 13:48:19,406 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-15 13:48:19,413 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 01:48:19" (1/1) ... [2022-04-15 13:48:19,413 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 01:48:19" (1/1) ... [2022-04-15 13:48:19,417 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 01:48:19" (1/1) ... [2022-04-15 13:48:19,418 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 01:48:19" (1/1) ... [2022-04-15 13:48:19,422 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 01:48:19" (1/1) ... [2022-04-15 13:48:19,424 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 01:48:19" (1/1) ... [2022-04-15 13:48:19,425 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 01:48:19" (1/1) ... [2022-04-15 13:48:19,426 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-15 13:48:19,427 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-15 13:48:19,427 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-15 13:48:19,427 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-15 13:48:19,428 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 01:48:19" (1/1) ... [2022-04-15 13:48:19,433 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 13:48:19,441 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 13:48:19,457 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-15 13:48:19,461 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-15 13:48:19,489 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-15 13:48:19,489 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-15 13:48:19,489 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-15 13:48:19,489 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-15 13:48:19,489 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-15 13:48:19,490 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-15 13:48:19,490 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-15 13:48:19,490 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-15 13:48:19,490 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-15 13:48:19,491 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-15 13:48:19,491 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_ushort [2022-04-15 13:48:19,491 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-15 13:48:19,492 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-15 13:48:19,492 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-15 13:48:19,492 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-15 13:48:19,492 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-15 13:48:19,492 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-15 13:48:19,492 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-15 13:48:19,492 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-15 13:48:19,492 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-15 13:48:19,552 INFO L234 CfgBuilder]: Building ICFG [2022-04-15 13:48:19,554 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-15 13:48:19,714 INFO L275 CfgBuilder]: Performing block encoding [2022-04-15 13:48:19,719 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-15 13:48:19,719 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-15 13:48:19,721 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 01:48:19 BoogieIcfgContainer [2022-04-15 13:48:19,721 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-15 13:48:19,722 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-15 13:48:19,722 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-15 13:48:19,736 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-15 13:48:19,737 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.04 01:48:19" (1/3) ... [2022-04-15 13:48:19,737 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1f95065e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 01:48:19, skipping insertion in model container [2022-04-15 13:48:19,737 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 01:48:19" (2/3) ... [2022-04-15 13:48:19,737 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1f95065e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 01:48:19, skipping insertion in model container [2022-04-15 13:48:19,737 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 01:48:19" (3/3) ... [2022-04-15 13:48:19,738 INFO L111 eAbstractionObserver]: Analyzing ICFG cohencu-ll_unwindbound2.c [2022-04-15 13:48:19,742 INFO L202 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-15 13:48:19,742 INFO L161 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-15 13:48:19,769 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-15 13:48:19,774 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-15 13:48:19,774 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-15 13:48:19,786 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 13:48:19,791 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-04-15 13:48:19,791 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 13:48:19,792 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 13:48:19,792 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 13:48:19,795 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 13:48:19,796 INFO L85 PathProgramCache]: Analyzing trace with hash 1839589780, now seen corresponding path program 1 times [2022-04-15 13:48:19,801 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 13:48:19,801 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [822757777] [2022-04-15 13:48:19,808 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 13:48:19,809 INFO L85 PathProgramCache]: Analyzing trace with hash 1839589780, now seen corresponding path program 2 times [2022-04-15 13:48:19,811 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 13:48:19,811 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [319339505] [2022-04-15 13:48:19,811 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 13:48:19,812 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 13:48:19,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 13:48:19,939 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 13:48:19,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 13:48:19,957 INFO L290 TraceCheckUtils]: 0: Hoare triple {39#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {34#true} is VALID [2022-04-15 13:48:19,958 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-15 13:48:19,958 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {34#true} {34#true} #81#return; {34#true} is VALID [2022-04-15 13:48:19,960 INFO L272 TraceCheckUtils]: 0: Hoare triple {34#true} call ULTIMATE.init(); {39#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 13:48:19,960 INFO L290 TraceCheckUtils]: 1: Hoare triple {39#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {34#true} is VALID [2022-04-15 13:48:19,960 INFO L290 TraceCheckUtils]: 2: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-15 13:48:19,961 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {34#true} {34#true} #81#return; {34#true} is VALID [2022-04-15 13:48:19,961 INFO L272 TraceCheckUtils]: 4: Hoare triple {34#true} call #t~ret6 := main(); {34#true} is VALID [2022-04-15 13:48:19,962 INFO L290 TraceCheckUtils]: 5: Hoare triple {34#true} havoc ~a~0;havoc ~n~0;havoc ~x~0;havoc ~y~0;havoc ~z~0;~a~0 := (if #t~nondet4 % 65536 % 65536 <= 32767 then #t~nondet4 % 65536 % 65536 else #t~nondet4 % 65536 % 65536 - 65536);havoc #t~nondet4;~n~0 := 0;~x~0 := 0;~y~0 := 1;~z~0 := 6; {34#true} is VALID [2022-04-15 13:48:19,962 INFO L290 TraceCheckUtils]: 6: Hoare triple {34#true} assume !true; {35#false} is VALID [2022-04-15 13:48:19,962 INFO L272 TraceCheckUtils]: 7: Hoare triple {35#false} call __VERIFIER_assert((if ~z~0 == 6 + 6 * ~n~0 then 1 else 0)); {35#false} is VALID [2022-04-15 13:48:19,963 INFO L290 TraceCheckUtils]: 8: Hoare triple {35#false} ~cond := #in~cond; {35#false} is VALID [2022-04-15 13:48:19,963 INFO L290 TraceCheckUtils]: 9: Hoare triple {35#false} assume 0 == ~cond; {35#false} is VALID [2022-04-15 13:48:19,963 INFO L290 TraceCheckUtils]: 10: Hoare triple {35#false} assume !false; {35#false} is VALID [2022-04-15 13:48:19,964 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-15 13:48:19,964 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 13:48:19,964 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [319339505] [2022-04-15 13:48:19,965 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [319339505] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 13:48:19,965 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 13:48:19,965 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 13:48:19,968 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 13:48:19,969 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [822757777] [2022-04-15 13:48:19,969 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [822757777] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 13:48:19,969 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 13:48:19,969 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 13:48:19,969 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1412897925] [2022-04-15 13:48:19,970 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 13:48:19,973 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-15 13:48:19,974 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 13:48:19,977 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-15 13:48:19,995 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-15 13:48:19,995 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-15 13:48:19,995 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 13:48:20,015 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-15 13:48:20,015 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 13:48:20,018 INFO L87 Difference]: Start difference. First operand has 31 states, 13 states have (on average 1.3846153846153846) internal successors, (18), 14 states have internal predecessors, (18), 13 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) 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-15 13:48:20,204 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:20,204 INFO L93 Difference]: Finished difference Result 57 states and 95 transitions. [2022-04-15 13:48:20,205 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-15 13:48:20,205 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-15 13:48:20,205 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 13:48:20,206 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-15 13:48:20,217 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 95 transitions. [2022-04-15 13:48:20,217 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-15 13:48:20,226 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 95 transitions. [2022-04-15 13:48:20,227 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 95 transitions. [2022-04-15 13:48:20,331 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 95 edges. 95 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:20,337 INFO L225 Difference]: With dead ends: 57 [2022-04-15 13:48:20,337 INFO L226 Difference]: Without dead ends: 27 [2022-04-15 13:48:20,339 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 13:48:20,341 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 20 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 20 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 13:48:20,342 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 45 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 13:48:20,353 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-04-15 13:48:20,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-04-15 13:48:20,364 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 13:48:20,364 INFO L82 GeneralOperation]: Start isEquivalent. First operand 27 states. Second operand has 26 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 13:48:20,365 INFO L74 IsIncluded]: Start isIncluded. First operand 27 states. Second operand has 26 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 13:48:20,365 INFO L87 Difference]: Start difference. First operand 27 states. Second operand has 26 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 13:48:20,373 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:20,373 INFO L93 Difference]: Finished difference Result 27 states and 38 transitions. [2022-04-15 13:48:20,373 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 38 transitions. [2022-04-15 13:48:20,374 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 13:48:20,374 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 13:48:20,374 INFO L74 IsIncluded]: Start isIncluded. First operand has 26 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 27 states. [2022-04-15 13:48:20,375 INFO L87 Difference]: Start difference. First operand has 26 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 27 states. [2022-04-15 13:48:20,377 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:20,377 INFO L93 Difference]: Finished difference Result 27 states and 38 transitions. [2022-04-15 13:48:20,377 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 38 transitions. [2022-04-15 13:48:20,378 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 13:48:20,378 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 13:48:20,378 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 13:48:20,378 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 13:48:20,379 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 13:48:20,380 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 37 transitions. [2022-04-15 13:48:20,381 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 37 transitions. Word has length 11 [2022-04-15 13:48:20,381 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 13:48:20,382 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 37 transitions. [2022-04-15 13:48:20,382 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-15 13:48:20,382 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 26 states and 37 transitions. [2022-04-15 13:48:20,413 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 37 edges. 37 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:20,413 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 37 transitions. [2022-04-15 13:48:20,414 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-15 13:48:20,414 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 13:48:20,414 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 13:48:20,414 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-15 13:48:20,414 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 13:48:20,415 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 13:48:20,415 INFO L85 PathProgramCache]: Analyzing trace with hash 660459433, now seen corresponding path program 1 times [2022-04-15 13:48:20,415 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 13:48:20,415 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1352112462] [2022-04-15 13:48:20,416 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 13:48:20,416 INFO L85 PathProgramCache]: Analyzing trace with hash 660459433, now seen corresponding path program 2 times [2022-04-15 13:48:20,416 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 13:48:20,416 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1997864833] [2022-04-15 13:48:20,416 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 13:48:20,417 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 13:48:20,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 13:48:20,499 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 13:48:20,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 13:48:20,515 INFO L290 TraceCheckUtils]: 0: Hoare triple {269#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {267#(= ~counter~0 0)} is VALID [2022-04-15 13:48:20,516 INFO L290 TraceCheckUtils]: 1: Hoare triple {267#(= ~counter~0 0)} assume true; {267#(= ~counter~0 0)} is VALID [2022-04-15 13:48:20,516 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {267#(= ~counter~0 0)} {262#true} #81#return; {267#(= ~counter~0 0)} is VALID [2022-04-15 13:48:20,517 INFO L272 TraceCheckUtils]: 0: Hoare triple {262#true} call ULTIMATE.init(); {269#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 13:48:20,517 INFO L290 TraceCheckUtils]: 1: Hoare triple {269#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {267#(= ~counter~0 0)} is VALID [2022-04-15 13:48:20,518 INFO L290 TraceCheckUtils]: 2: Hoare triple {267#(= ~counter~0 0)} assume true; {267#(= ~counter~0 0)} is VALID [2022-04-15 13:48:20,518 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {267#(= ~counter~0 0)} {262#true} #81#return; {267#(= ~counter~0 0)} is VALID [2022-04-15 13:48:20,518 INFO L272 TraceCheckUtils]: 4: Hoare triple {267#(= ~counter~0 0)} call #t~ret6 := main(); {267#(= ~counter~0 0)} is VALID [2022-04-15 13:48:20,519 INFO L290 TraceCheckUtils]: 5: Hoare triple {267#(= ~counter~0 0)} havoc ~a~0;havoc ~n~0;havoc ~x~0;havoc ~y~0;havoc ~z~0;~a~0 := (if #t~nondet4 % 65536 % 65536 <= 32767 then #t~nondet4 % 65536 % 65536 else #t~nondet4 % 65536 % 65536 - 65536);havoc #t~nondet4;~n~0 := 0;~x~0 := 0;~y~0 := 1;~z~0 := 6; {267#(= ~counter~0 0)} is VALID [2022-04-15 13:48:20,519 INFO L290 TraceCheckUtils]: 6: Hoare triple {267#(= ~counter~0 0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {268#(= |main_#t~post5| 0)} is VALID [2022-04-15 13:48:20,520 INFO L290 TraceCheckUtils]: 7: Hoare triple {268#(= |main_#t~post5| 0)} assume !(#t~post5 < 2);havoc #t~post5; {263#false} is VALID [2022-04-15 13:48:20,520 INFO L272 TraceCheckUtils]: 8: Hoare triple {263#false} call __VERIFIER_assert((if ~z~0 == 6 + 6 * ~n~0 then 1 else 0)); {263#false} is VALID [2022-04-15 13:48:20,520 INFO L290 TraceCheckUtils]: 9: Hoare triple {263#false} ~cond := #in~cond; {263#false} is VALID [2022-04-15 13:48:20,520 INFO L290 TraceCheckUtils]: 10: Hoare triple {263#false} assume 0 == ~cond; {263#false} is VALID [2022-04-15 13:48:20,520 INFO L290 TraceCheckUtils]: 11: Hoare triple {263#false} assume !false; {263#false} is VALID [2022-04-15 13:48:20,521 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-15 13:48:20,521 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 13:48:20,521 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1997864833] [2022-04-15 13:48:20,521 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1997864833] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 13:48:20,521 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 13:48:20,521 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-15 13:48:20,522 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 13:48:20,522 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1352112462] [2022-04-15 13:48:20,522 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1352112462] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 13:48:20,522 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 13:48:20,522 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-15 13:48:20,522 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [474053029] [2022-04-15 13:48:20,522 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 13:48:20,523 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 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 12 [2022-04-15 13:48:20,523 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 13:48:20,523 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 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-15 13:48:20,532 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 12 edges. 12 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:20,532 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 13:48:20,532 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 13:48:20,533 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 13:48:20,533 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 13:48:20,533 INFO L87 Difference]: Start difference. First operand 26 states and 37 transitions. Second operand has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 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-15 13:48:20,782 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:20,782 INFO L93 Difference]: Finished difference Result 40 states and 56 transitions. [2022-04-15 13:48:20,782 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-15 13:48:20,783 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 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 12 [2022-04-15 13:48:20,783 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 13:48:20,783 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 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-15 13:48:20,788 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 56 transitions. [2022-04-15 13:48:20,788 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 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-15 13:48:20,795 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 56 transitions. [2022-04-15 13:48:20,795 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 56 transitions. [2022-04-15 13:48:20,843 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 56 edges. 56 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:20,845 INFO L225 Difference]: With dead ends: 40 [2022-04-15 13:48:20,846 INFO L226 Difference]: Without dead ends: 28 [2022-04-15 13:48:20,847 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-15 13:48:20,850 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 6 mSDsluCounter, 34 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 67 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-15 13:48:20,850 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 69 Invalid, 67 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-15 13:48:20,853 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2022-04-15 13:48:20,861 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2022-04-15 13:48:20,861 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 13:48:20,861 INFO L82 GeneralOperation]: Start isEquivalent. First operand 28 states. Second operand has 28 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 13:48:20,862 INFO L74 IsIncluded]: Start isIncluded. First operand 28 states. Second operand has 28 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 13:48:20,863 INFO L87 Difference]: Start difference. First operand 28 states. Second operand has 28 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 13:48:20,867 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:20,868 INFO L93 Difference]: Finished difference Result 28 states and 39 transitions. [2022-04-15 13:48:20,868 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 39 transitions. [2022-04-15 13:48:20,874 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 13:48:20,874 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 13:48:20,875 INFO L74 IsIncluded]: Start isIncluded. First operand has 28 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 28 states. [2022-04-15 13:48:20,875 INFO L87 Difference]: Start difference. First operand has 28 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 28 states. [2022-04-15 13:48:20,877 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:20,877 INFO L93 Difference]: Finished difference Result 28 states and 39 transitions. [2022-04-15 13:48:20,877 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 39 transitions. [2022-04-15 13:48:20,877 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 13:48:20,877 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 13:48:20,878 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 13:48:20,878 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 13:48:20,878 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 12 states have (on average 1.25) internal successors, (15), 13 states have internal predecessors, (15), 13 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 13:48:20,879 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 39 transitions. [2022-04-15 13:48:20,879 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 39 transitions. Word has length 12 [2022-04-15 13:48:20,879 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 13:48:20,880 INFO L478 AbstractCegarLoop]: Abstraction has 28 states and 39 transitions. [2022-04-15 13:48:20,880 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 3 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-15 13:48:20,880 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 28 states and 39 transitions. [2022-04-15 13:48:20,909 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-15 13:48:20,909 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 39 transitions. [2022-04-15 13:48:20,910 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-15 13:48:20,910 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 13:48:20,910 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 13:48:20,910 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-15 13:48:20,910 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 13:48:20,911 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 13:48:20,911 INFO L85 PathProgramCache]: Analyzing trace with hash 662008565, now seen corresponding path program 1 times [2022-04-15 13:48:20,911 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 13:48:20,911 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1202265526] [2022-04-15 13:48:20,911 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 13:48:20,912 INFO L85 PathProgramCache]: Analyzing trace with hash 662008565, now seen corresponding path program 2 times [2022-04-15 13:48:20,912 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 13:48:20,912 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1884616171] [2022-04-15 13:48:20,912 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 13:48:20,912 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 13:48:20,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 13:48:20,981 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 13:48:20,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 13:48:20,987 INFO L290 TraceCheckUtils]: 0: Hoare triple {474#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {466#true} is VALID [2022-04-15 13:48:20,988 INFO L290 TraceCheckUtils]: 1: Hoare triple {466#true} assume true; {466#true} is VALID [2022-04-15 13:48:20,988 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {466#true} {466#true} #81#return; {466#true} is VALID [2022-04-15 13:48:20,988 INFO L272 TraceCheckUtils]: 0: Hoare triple {466#true} call ULTIMATE.init(); {474#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 13:48:20,989 INFO L290 TraceCheckUtils]: 1: Hoare triple {474#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {466#true} is VALID [2022-04-15 13:48:20,989 INFO L290 TraceCheckUtils]: 2: Hoare triple {466#true} assume true; {466#true} is VALID [2022-04-15 13:48:20,989 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {466#true} {466#true} #81#return; {466#true} is VALID [2022-04-15 13:48:20,989 INFO L272 TraceCheckUtils]: 4: Hoare triple {466#true} call #t~ret6 := main(); {466#true} is VALID [2022-04-15 13:48:20,989 INFO L290 TraceCheckUtils]: 5: Hoare triple {466#true} havoc ~a~0;havoc ~n~0;havoc ~x~0;havoc ~y~0;havoc ~z~0;~a~0 := (if #t~nondet4 % 65536 % 65536 <= 32767 then #t~nondet4 % 65536 % 65536 else #t~nondet4 % 65536 % 65536 - 65536);havoc #t~nondet4;~n~0 := 0;~x~0 := 0;~y~0 := 1;~z~0 := 6; {471#(= (+ (* main_~n~0 6) 6) main_~z~0)} is VALID [2022-04-15 13:48:20,990 INFO L290 TraceCheckUtils]: 6: Hoare triple {471#(= (+ (* main_~n~0 6) 6) main_~z~0)} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {471#(= (+ (* main_~n~0 6) 6) main_~z~0)} is VALID [2022-04-15 13:48:20,990 INFO L290 TraceCheckUtils]: 7: Hoare triple {471#(= (+ (* main_~n~0 6) 6) main_~z~0)} assume !!(#t~post5 < 2);havoc #t~post5; {471#(= (+ (* main_~n~0 6) 6) main_~z~0)} is VALID [2022-04-15 13:48:20,991 INFO L272 TraceCheckUtils]: 8: Hoare triple {471#(= (+ (* main_~n~0 6) 6) main_~z~0)} call __VERIFIER_assert((if ~z~0 == 6 + 6 * ~n~0 then 1 else 0)); {472#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 13:48:20,991 INFO L290 TraceCheckUtils]: 9: Hoare triple {472#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {473#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 13:48:20,992 INFO L290 TraceCheckUtils]: 10: Hoare triple {473#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {467#false} is VALID [2022-04-15 13:48:20,992 INFO L290 TraceCheckUtils]: 11: Hoare triple {467#false} assume !false; {467#false} is VALID [2022-04-15 13:48:20,992 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-15 13:48:20,992 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 13:48:20,992 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1884616171] [2022-04-15 13:48:20,993 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1884616171] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 13:48:20,993 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 13:48:20,993 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 13:48:20,993 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 13:48:20,993 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1202265526] [2022-04-15 13:48:20,993 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1202265526] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 13:48:20,993 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 13:48:20,993 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-15 13:48:20,993 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [910721713] [2022-04-15 13:48:20,993 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 13:48:20,994 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 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 12 [2022-04-15 13:48:20,994 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 13:48:20,994 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 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-15 13:48:21,002 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 12 edges. 12 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:21,002 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-15 13:48:21,002 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 13:48:21,002 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-15 13:48:21,003 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-15 13:48:21,003 INFO L87 Difference]: Start difference. First operand 28 states and 39 transitions. Second operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 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-15 13:48:21,305 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:21,305 INFO L93 Difference]: Finished difference Result 34 states and 44 transitions. [2022-04-15 13:48:21,305 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-15 13:48:21,305 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 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 12 [2022-04-15 13:48:21,305 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 13:48:21,306 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 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-15 13:48:21,308 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 43 transitions. [2022-04-15 13:48:21,308 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 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-15 13:48:21,312 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 43 transitions. [2022-04-15 13:48:21,312 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 43 transitions. [2022-04-15 13:48:21,357 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 43 edges. 43 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:21,359 INFO L225 Difference]: With dead ends: 34 [2022-04-15 13:48:21,360 INFO L226 Difference]: Without dead ends: 32 [2022-04-15 13:48:21,360 INFO L912 BasicCegarLoop]: 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-15 13:48:21,362 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 17 mSDsluCounter, 21 mSDsCounter, 0 mSdLazyCounter, 95 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 110 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 95 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-15 13:48:21,365 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 51 Invalid, 110 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 95 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-15 13:48:21,366 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-15 13:48:21,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-04-15 13:48:21,375 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 13:48:21,376 INFO L82 GeneralOperation]: Start isEquivalent. First operand 32 states. Second operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 13:48:21,378 INFO L74 IsIncluded]: Start isIncluded. First operand 32 states. Second operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 13:48:21,378 INFO L87 Difference]: Start difference. First operand 32 states. Second operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 13:48:21,383 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:21,383 INFO L93 Difference]: Finished difference Result 32 states and 42 transitions. [2022-04-15 13:48:21,383 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-04-15 13:48:21,384 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 13:48:21,384 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 13:48:21,384 INFO L74 IsIncluded]: Start isIncluded. First operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 32 states. [2022-04-15 13:48:21,384 INFO L87 Difference]: Start difference. First operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 32 states. [2022-04-15 13:48:21,389 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:21,389 INFO L93 Difference]: Finished difference Result 32 states and 42 transitions. [2022-04-15 13:48:21,390 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-04-15 13:48:21,390 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 13:48:21,390 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 13:48:21,390 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 13:48:21,390 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 13:48:21,390 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 13:48:21,392 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 42 transitions. [2022-04-15 13:48:21,392 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 42 transitions. Word has length 12 [2022-04-15 13:48:21,393 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 13:48:21,393 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 42 transitions. [2022-04-15 13:48:21,393 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.3333333333333333) internal successors, (8), 4 states have internal predecessors, (8), 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-15 13:48:21,393 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 32 states and 42 transitions. [2022-04-15 13:48:21,425 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-15 13:48:21,425 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-04-15 13:48:21,426 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-15 13:48:21,426 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 13:48:21,426 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 13:48:21,426 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-15 13:48:21,426 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 13:48:21,426 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 13:48:21,427 INFO L85 PathProgramCache]: Analyzing trace with hash 2023221563, now seen corresponding path program 1 times [2022-04-15 13:48:21,427 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 13:48:21,427 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1588437632] [2022-04-15 13:48:21,427 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 13:48:21,427 INFO L85 PathProgramCache]: Analyzing trace with hash 2023221563, now seen corresponding path program 2 times [2022-04-15 13:48:21,427 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 13:48:21,428 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1140862050] [2022-04-15 13:48:21,428 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 13:48:21,428 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 13:48:21,443 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 13:48:21,443 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [738883541] [2022-04-15 13:48:21,443 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 13:48:21,443 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 13:48:21,443 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 13:48:21,458 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 13:48:21,459 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-15 13:48:21,494 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 13:48:21,494 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 13:48:21,495 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 13:48:21,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 13:48:21,503 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 13:48:21,634 INFO L272 TraceCheckUtils]: 0: Hoare triple {681#true} call ULTIMATE.init(); {681#true} is VALID [2022-04-15 13:48:21,635 INFO L290 TraceCheckUtils]: 1: Hoare triple {681#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {681#true} is VALID [2022-04-15 13:48:21,635 INFO L290 TraceCheckUtils]: 2: Hoare triple {681#true} assume true; {681#true} is VALID [2022-04-15 13:48:21,635 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {681#true} {681#true} #81#return; {681#true} is VALID [2022-04-15 13:48:21,635 INFO L272 TraceCheckUtils]: 4: Hoare triple {681#true} call #t~ret6 := main(); {681#true} is VALID [2022-04-15 13:48:21,636 INFO L290 TraceCheckUtils]: 5: Hoare triple {681#true} havoc ~a~0;havoc ~n~0;havoc ~x~0;havoc ~y~0;havoc ~z~0;~a~0 := (if #t~nondet4 % 65536 % 65536 <= 32767 then #t~nondet4 % 65536 % 65536 else #t~nondet4 % 65536 % 65536 - 65536);havoc #t~nondet4;~n~0 := 0;~x~0 := 0;~y~0 := 1;~z~0 := 6; {701#(and (= main_~n~0 0) (= main_~y~0 1))} is VALID [2022-04-15 13:48:21,636 INFO L290 TraceCheckUtils]: 6: Hoare triple {701#(and (= main_~n~0 0) (= main_~y~0 1))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {701#(and (= main_~n~0 0) (= main_~y~0 1))} is VALID [2022-04-15 13:48:21,637 INFO L290 TraceCheckUtils]: 7: Hoare triple {701#(and (= main_~n~0 0) (= main_~y~0 1))} assume !!(#t~post5 < 2);havoc #t~post5; {701#(and (= main_~n~0 0) (= main_~y~0 1))} is VALID [2022-04-15 13:48:21,637 INFO L272 TraceCheckUtils]: 8: Hoare triple {701#(and (= main_~n~0 0) (= main_~y~0 1))} call __VERIFIER_assert((if ~z~0 == 6 + 6 * ~n~0 then 1 else 0)); {681#true} is VALID [2022-04-15 13:48:21,637 INFO L290 TraceCheckUtils]: 9: Hoare triple {681#true} ~cond := #in~cond; {681#true} is VALID [2022-04-15 13:48:21,637 INFO L290 TraceCheckUtils]: 10: Hoare triple {681#true} assume !(0 == ~cond); {681#true} is VALID [2022-04-15 13:48:21,637 INFO L290 TraceCheckUtils]: 11: Hoare triple {681#true} assume true; {681#true} is VALID [2022-04-15 13:48:21,638 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {681#true} {701#(and (= main_~n~0 0) (= main_~y~0 1))} #59#return; {701#(and (= main_~n~0 0) (= main_~y~0 1))} is VALID [2022-04-15 13:48:21,639 INFO L272 TraceCheckUtils]: 13: Hoare triple {701#(and (= main_~n~0 0) (= main_~y~0 1))} call __VERIFIER_assert((if ~y~0 == 1 + (3 * ~n~0 * ~n~0 + 3 * ~n~0) then 1 else 0)); {726#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 13:48:21,639 INFO L290 TraceCheckUtils]: 14: Hoare triple {726#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {730#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 13:48:21,640 INFO L290 TraceCheckUtils]: 15: Hoare triple {730#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {682#false} is VALID [2022-04-15 13:48:21,640 INFO L290 TraceCheckUtils]: 16: Hoare triple {682#false} assume !false; {682#false} is VALID [2022-04-15 13:48:21,640 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-15 13:48:21,640 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 13:48:21,640 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 13:48:21,641 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1140862050] [2022-04-15 13:48:21,641 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 13:48:21,641 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [738883541] [2022-04-15 13:48:21,641 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [738883541] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 13:48:21,641 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 13:48:21,641 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 13:48:21,641 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 13:48:21,642 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1588437632] [2022-04-15 13:48:21,642 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1588437632] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 13:48:21,642 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 13:48:21,642 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 13:48:21,642 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1031943784] [2022-04-15 13:48:21,642 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 13:48:21,642 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, (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 17 [2022-04-15 13:48:21,643 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 13:48:21,643 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, (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-15 13:48:21,655 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 17 edges. 17 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:21,656 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 13:48:21,656 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 13:48:21,656 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 13:48:21,656 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 13:48:21,656 INFO L87 Difference]: Start difference. First operand 32 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, (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-15 13:48:21,913 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:21,913 INFO L93 Difference]: Finished difference Result 50 states and 70 transitions. [2022-04-15 13:48:21,913 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 13:48:21,913 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, (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 17 [2022-04-15 13:48:21,913 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 13:48:21,913 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, (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-15 13:48:21,915 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-15 13:48:21,915 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, (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-15 13:48:21,916 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-15 13:48:21,916 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 67 transitions. [2022-04-15 13:48:21,970 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 67 edges. 67 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:21,972 INFO L225 Difference]: With dead ends: 50 [2022-04-15 13:48:21,972 INFO L226 Difference]: Without dead ends: 48 [2022-04-15 13:48:21,972 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-15 13:48:21,973 INFO L913 BasicCegarLoop]: 49 mSDtfsCounter, 6 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-15 13:48:21,973 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 141 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-15 13:48:21,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-04-15 13:48:21,992 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 38. [2022-04-15 13:48:21,992 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 13:48:21,992 INFO L82 GeneralOperation]: Start isEquivalent. First operand 48 states. Second operand has 38 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 13:48:21,993 INFO L74 IsIncluded]: Start isIncluded. First operand 48 states. Second operand has 38 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 13:48:21,993 INFO L87 Difference]: Start difference. First operand 48 states. Second operand has 38 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 13:48:21,995 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:21,995 INFO L93 Difference]: Finished difference Result 48 states and 68 transitions. [2022-04-15 13:48:21,995 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 68 transitions. [2022-04-15 13:48:21,996 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 13:48:21,996 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 13:48:21,996 INFO L74 IsIncluded]: Start isIncluded. First operand has 38 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 48 states. [2022-04-15 13:48:21,996 INFO L87 Difference]: Start difference. First operand has 38 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 48 states. [2022-04-15 13:48:21,998 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:21,998 INFO L93 Difference]: Finished difference Result 48 states and 68 transitions. [2022-04-15 13:48:21,998 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 68 transitions. [2022-04-15 13:48:21,999 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 13:48:21,999 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 13:48:21,999 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 13:48:21,999 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 13:48:21,999 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 13:48:22,000 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 49 transitions. [2022-04-15 13:48:22,001 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 49 transitions. Word has length 17 [2022-04-15 13:48:22,001 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 13:48:22,001 INFO L478 AbstractCegarLoop]: Abstraction has 38 states and 49 transitions. [2022-04-15 13:48:22,001 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (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-15 13:48:22,001 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 38 states and 49 transitions. [2022-04-15 13:48:22,053 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 49 edges. 49 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:22,053 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 49 transitions. [2022-04-15 13:48:22,053 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-15 13:48:22,053 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 13:48:22,054 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 13:48:22,078 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-15 13:48:22,263 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 13:48:22,264 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 13:48:22,264 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 13:48:22,264 INFO L85 PathProgramCache]: Analyzing trace with hash 1612678773, now seen corresponding path program 1 times [2022-04-15 13:48:22,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 13:48:22,264 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1025588958] [2022-04-15 13:48:22,265 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 13:48:22,265 INFO L85 PathProgramCache]: Analyzing trace with hash 1612678773, now seen corresponding path program 2 times [2022-04-15 13:48:22,265 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 13:48:22,265 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [799315079] [2022-04-15 13:48:22,265 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 13:48:22,265 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 13:48:22,276 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 13:48:22,277 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1186842143] [2022-04-15 13:48:22,277 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 13:48:22,277 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 13:48:22,277 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 13:48:22,278 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 13:48:22,279 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-15 13:48:22,309 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 13:48:22,310 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 13:48:22,315 INFO L263 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 13:48:22,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 13:48:22,320 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 13:48:22,462 INFO L272 TraceCheckUtils]: 0: Hoare triple {1010#true} call ULTIMATE.init(); {1010#true} is VALID [2022-04-15 13:48:22,462 INFO L290 TraceCheckUtils]: 1: Hoare triple {1010#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1010#true} is VALID [2022-04-15 13:48:22,463 INFO L290 TraceCheckUtils]: 2: Hoare triple {1010#true} assume true; {1010#true} is VALID [2022-04-15 13:48:22,463 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1010#true} {1010#true} #81#return; {1010#true} is VALID [2022-04-15 13:48:22,463 INFO L272 TraceCheckUtils]: 4: Hoare triple {1010#true} call #t~ret6 := main(); {1010#true} is VALID [2022-04-15 13:48:22,464 INFO L290 TraceCheckUtils]: 5: Hoare triple {1010#true} havoc ~a~0;havoc ~n~0;havoc ~x~0;havoc ~y~0;havoc ~z~0;~a~0 := (if #t~nondet4 % 65536 % 65536 <= 32767 then #t~nondet4 % 65536 % 65536 else #t~nondet4 % 65536 % 65536 - 65536);havoc #t~nondet4;~n~0 := 0;~x~0 := 0;~y~0 := 1;~z~0 := 6; {1030#(and (= main_~x~0 0) (= main_~n~0 0))} is VALID [2022-04-15 13:48:22,465 INFO L290 TraceCheckUtils]: 6: Hoare triple {1030#(and (= main_~x~0 0) (= main_~n~0 0))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1030#(and (= main_~x~0 0) (= main_~n~0 0))} is VALID [2022-04-15 13:48:22,466 INFO L290 TraceCheckUtils]: 7: Hoare triple {1030#(and (= main_~x~0 0) (= main_~n~0 0))} assume !!(#t~post5 < 2);havoc #t~post5; {1030#(and (= main_~x~0 0) (= main_~n~0 0))} is VALID [2022-04-15 13:48:22,466 INFO L272 TraceCheckUtils]: 8: Hoare triple {1030#(and (= main_~x~0 0) (= main_~n~0 0))} call __VERIFIER_assert((if ~z~0 == 6 + 6 * ~n~0 then 1 else 0)); {1010#true} is VALID [2022-04-15 13:48:22,466 INFO L290 TraceCheckUtils]: 9: Hoare triple {1010#true} ~cond := #in~cond; {1010#true} is VALID [2022-04-15 13:48:22,466 INFO L290 TraceCheckUtils]: 10: Hoare triple {1010#true} assume !(0 == ~cond); {1010#true} is VALID [2022-04-15 13:48:22,466 INFO L290 TraceCheckUtils]: 11: Hoare triple {1010#true} assume true; {1010#true} is VALID [2022-04-15 13:48:22,467 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {1010#true} {1030#(and (= main_~x~0 0) (= main_~n~0 0))} #59#return; {1030#(and (= main_~x~0 0) (= main_~n~0 0))} is VALID [2022-04-15 13:48:22,467 INFO L272 TraceCheckUtils]: 13: Hoare triple {1030#(and (= main_~x~0 0) (= main_~n~0 0))} call __VERIFIER_assert((if ~y~0 == 1 + (3 * ~n~0 * ~n~0 + 3 * ~n~0) then 1 else 0)); {1010#true} is VALID [2022-04-15 13:48:22,467 INFO L290 TraceCheckUtils]: 14: Hoare triple {1010#true} ~cond := #in~cond; {1010#true} is VALID [2022-04-15 13:48:22,467 INFO L290 TraceCheckUtils]: 15: Hoare triple {1010#true} assume !(0 == ~cond); {1010#true} is VALID [2022-04-15 13:48:22,468 INFO L290 TraceCheckUtils]: 16: Hoare triple {1010#true} assume true; {1010#true} is VALID [2022-04-15 13:48:22,471 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {1010#true} {1030#(and (= main_~x~0 0) (= main_~n~0 0))} #61#return; {1030#(and (= main_~x~0 0) (= main_~n~0 0))} is VALID [2022-04-15 13:48:22,472 INFO L272 TraceCheckUtils]: 18: Hoare triple {1030#(and (= main_~x~0 0) (= main_~n~0 0))} call __VERIFIER_assert((if ~x~0 == ~n~0 * ~n~0 * ~n~0 then 1 else 0)); {1070#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 13:48:22,472 INFO L290 TraceCheckUtils]: 19: Hoare triple {1070#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1074#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 13:48:22,473 INFO L290 TraceCheckUtils]: 20: Hoare triple {1074#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1011#false} is VALID [2022-04-15 13:48:22,473 INFO L290 TraceCheckUtils]: 21: Hoare triple {1011#false} assume !false; {1011#false} is VALID [2022-04-15 13:48:22,473 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-15 13:48:22,473 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 13:48:22,473 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 13:48:22,474 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [799315079] [2022-04-15 13:48:22,474 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 13:48:22,474 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1186842143] [2022-04-15 13:48:22,474 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1186842143] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 13:48:22,474 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 13:48:22,474 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 13:48:22,474 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 13:48:22,474 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1025588958] [2022-04-15 13:48:22,474 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1025588958] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 13:48:22,475 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 13:48:22,475 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 13:48:22,475 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [624318892] [2022-04-15 13:48:22,475 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 13:48:22,475 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, (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 22 [2022-04-15 13:48:22,475 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 13:48:22,475 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, (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-15 13:48:22,491 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 19 edges. 19 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:22,491 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 13:48:22,491 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 13:48:22,491 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 13:48:22,492 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 13:48:22,492 INFO L87 Difference]: Start difference. First operand 38 states and 49 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, (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-15 13:48:22,682 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:22,683 INFO L93 Difference]: Finished difference Result 54 states and 73 transitions. [2022-04-15 13:48:22,683 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 13:48:22,683 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, (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 22 [2022-04-15 13:48:22,684 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 13:48:22,684 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, (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-15 13:48:22,685 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-15 13:48:22,685 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, (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-15 13:48:22,686 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-15 13:48:22,686 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 67 transitions. [2022-04-15 13:48:22,744 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 67 edges. 67 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:22,745 INFO L225 Difference]: With dead ends: 54 [2022-04-15 13:48:22,746 INFO L226 Difference]: Without dead ends: 52 [2022-04-15 13:48:22,746 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-15 13:48:22,749 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 6 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-15 13:48:22,749 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 134 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-15 13:48:22,750 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-15 13:48:22,768 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 48. [2022-04-15 13:48:22,769 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 13:48:22,769 INFO L82 GeneralOperation]: Start isEquivalent. First operand 52 states. Second operand has 48 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 20 states have call successors, (20), 6 states have call predecessors, (20), 5 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-15 13:48:22,770 INFO L74 IsIncluded]: Start isIncluded. First operand 52 states. Second operand has 48 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 20 states have call successors, (20), 6 states have call predecessors, (20), 5 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-15 13:48:22,772 INFO L87 Difference]: Start difference. First operand 52 states. Second operand has 48 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 20 states have call successors, (20), 6 states have call predecessors, (20), 5 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-15 13:48:22,774 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:22,775 INFO L93 Difference]: Finished difference Result 52 states and 71 transitions. [2022-04-15 13:48:22,775 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 71 transitions. [2022-04-15 13:48:22,775 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 13:48:22,775 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 13:48:22,776 INFO L74 IsIncluded]: Start isIncluded. First operand has 48 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 20 states have call successors, (20), 6 states have call predecessors, (20), 5 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) Second operand 52 states. [2022-04-15 13:48:22,776 INFO L87 Difference]: Start difference. First operand has 48 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 20 states have call successors, (20), 6 states have call predecessors, (20), 5 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) Second operand 52 states. [2022-04-15 13:48:22,779 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:22,779 INFO L93 Difference]: Finished difference Result 52 states and 71 transitions. [2022-04-15 13:48:22,779 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 71 transitions. [2022-04-15 13:48:22,780 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 13:48:22,780 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 13:48:22,780 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 13:48:22,780 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 13:48:22,781 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 20 states have call successors, (20), 6 states have call predecessors, (20), 5 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-15 13:48:22,783 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 64 transitions. [2022-04-15 13:48:22,783 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 64 transitions. Word has length 22 [2022-04-15 13:48:22,783 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 13:48:22,783 INFO L478 AbstractCegarLoop]: Abstraction has 48 states and 64 transitions. [2022-04-15 13:48:22,783 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (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-15 13:48:22,783 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 48 states and 64 transitions. [2022-04-15 13:48:22,839 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 64 edges. 64 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:22,840 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 64 transitions. [2022-04-15 13:48:22,840 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-04-15 13:48:22,840 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 13:48:22,840 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 13:48:22,858 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-15 13:48:23,051 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 13:48:23,052 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 13:48:23,052 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 13:48:23,052 INFO L85 PathProgramCache]: Analyzing trace with hash 1625830715, now seen corresponding path program 1 times [2022-04-15 13:48:23,052 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 13:48:23,052 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2112573739] [2022-04-15 13:48:23,053 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 13:48:23,053 INFO L85 PathProgramCache]: Analyzing trace with hash 1625830715, now seen corresponding path program 2 times [2022-04-15 13:48:23,053 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 13:48:23,053 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [220492127] [2022-04-15 13:48:23,053 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 13:48:23,053 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 13:48:23,068 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 13:48:23,068 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [853879483] [2022-04-15 13:48:23,068 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 13:48:23,068 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 13:48:23,069 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 13:48:23,083 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 13:48:23,085 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-15 13:48:23,119 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 13:48:23,119 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 13:48:23,120 INFO L263 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-15 13:48:23,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 13:48:23,128 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 13:48:23,253 INFO L272 TraceCheckUtils]: 0: Hoare triple {1390#true} call ULTIMATE.init(); {1390#true} is VALID [2022-04-15 13:48:23,253 INFO L290 TraceCheckUtils]: 1: Hoare triple {1390#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {1390#true} is VALID [2022-04-15 13:48:23,253 INFO L290 TraceCheckUtils]: 2: Hoare triple {1390#true} assume true; {1390#true} is VALID [2022-04-15 13:48:23,253 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1390#true} {1390#true} #81#return; {1390#true} is VALID [2022-04-15 13:48:23,254 INFO L272 TraceCheckUtils]: 4: Hoare triple {1390#true} call #t~ret6 := main(); {1390#true} is VALID [2022-04-15 13:48:23,255 INFO L290 TraceCheckUtils]: 5: Hoare triple {1390#true} havoc ~a~0;havoc ~n~0;havoc ~x~0;havoc ~y~0;havoc ~z~0;~a~0 := (if #t~nondet4 % 65536 % 65536 <= 32767 then #t~nondet4 % 65536 % 65536 else #t~nondet4 % 65536 % 65536 - 65536);havoc #t~nondet4;~n~0 := 0;~x~0 := 0;~y~0 := 1;~z~0 := 6; {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} is VALID [2022-04-15 13:48:23,256 INFO L290 TraceCheckUtils]: 6: Hoare triple {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} #t~post5 := ~counter~0;~counter~0 := 1 + #t~post5; {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} is VALID [2022-04-15 13:48:23,256 INFO L290 TraceCheckUtils]: 7: Hoare triple {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} assume !!(#t~post5 < 2);havoc #t~post5; {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} is VALID [2022-04-15 13:48:23,256 INFO L272 TraceCheckUtils]: 8: Hoare triple {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} call __VERIFIER_assert((if ~z~0 == 6 + 6 * ~n~0 then 1 else 0)); {1390#true} is VALID [2022-04-15 13:48:23,256 INFO L290 TraceCheckUtils]: 9: Hoare triple {1390#true} ~cond := #in~cond; {1390#true} is VALID [2022-04-15 13:48:23,256 INFO L290 TraceCheckUtils]: 10: Hoare triple {1390#true} assume !(0 == ~cond); {1390#true} is VALID [2022-04-15 13:48:23,256 INFO L290 TraceCheckUtils]: 11: Hoare triple {1390#true} assume true; {1390#true} is VALID [2022-04-15 13:48:23,257 INFO L284 TraceCheckUtils]: 12: Hoare quadruple {1390#true} {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} #59#return; {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} is VALID [2022-04-15 13:48:23,257 INFO L272 TraceCheckUtils]: 13: Hoare triple {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} call __VERIFIER_assert((if ~y~0 == 1 + (3 * ~n~0 * ~n~0 + 3 * ~n~0) then 1 else 0)); {1390#true} is VALID [2022-04-15 13:48:23,257 INFO L290 TraceCheckUtils]: 14: Hoare triple {1390#true} ~cond := #in~cond; {1390#true} is VALID [2022-04-15 13:48:23,258 INFO L290 TraceCheckUtils]: 15: Hoare triple {1390#true} assume !(0 == ~cond); {1390#true} is VALID [2022-04-15 13:48:23,258 INFO L290 TraceCheckUtils]: 16: Hoare triple {1390#true} assume true; {1390#true} is VALID [2022-04-15 13:48:23,258 INFO L284 TraceCheckUtils]: 17: Hoare quadruple {1390#true} {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} #61#return; {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} is VALID [2022-04-15 13:48:23,258 INFO L272 TraceCheckUtils]: 18: Hoare triple {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} call __VERIFIER_assert((if ~x~0 == ~n~0 * ~n~0 * ~n~0 then 1 else 0)); {1390#true} is VALID [2022-04-15 13:48:23,258 INFO L290 TraceCheckUtils]: 19: Hoare triple {1390#true} ~cond := #in~cond; {1390#true} is VALID [2022-04-15 13:48:23,259 INFO L290 TraceCheckUtils]: 20: Hoare triple {1390#true} assume !(0 == ~cond); {1390#true} is VALID [2022-04-15 13:48:23,259 INFO L290 TraceCheckUtils]: 21: Hoare triple {1390#true} assume true; {1390#true} is VALID [2022-04-15 13:48:23,260 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1390#true} {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} #63#return; {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} is VALID [2022-04-15 13:48:23,261 INFO L272 TraceCheckUtils]: 23: Hoare triple {1410#(and (= main_~x~0 0) (= main_~y~0 1) (= main_~z~0 6))} call __VERIFIER_assert((if 0 == ~y~0 * ~z~0 - 18 * ~x~0 - 12 * ~y~0 + 2 * ~z~0 - 6 then 1 else 0)); {1465#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 13:48:23,262 INFO L290 TraceCheckUtils]: 24: Hoare triple {1465#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1469#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 13:48:23,262 INFO L290 TraceCheckUtils]: 25: Hoare triple {1469#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1391#false} is VALID [2022-04-15 13:48:23,262 INFO L290 TraceCheckUtils]: 26: Hoare triple {1391#false} assume !false; {1391#false} is VALID [2022-04-15 13:48:23,262 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-15 13:48:23,262 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 13:48:23,263 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 13:48:23,263 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [220492127] [2022-04-15 13:48:23,263 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 13:48:23,263 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [853879483] [2022-04-15 13:48:23,263 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [853879483] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 13:48:23,263 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 13:48:23,263 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 13:48:23,263 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 13:48:23,263 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2112573739] [2022-04-15 13:48:23,263 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2112573739] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 13:48:23,263 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 13:48:23,264 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 13:48:23,264 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [573991400] [2022-04-15 13:48:23,264 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 13:48:23,264 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 27 [2022-04-15 13:48:23,264 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 13:48:23,264 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-15 13:48:23,277 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-15 13:48:23,278 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 13:48:23,278 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 13:48:23,278 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 13:48:23,278 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 13:48:23,278 INFO L87 Difference]: Start difference. First operand 48 states and 64 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-15 13:48:23,581 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:23,582 INFO L93 Difference]: Finished difference Result 62 states and 79 transitions. [2022-04-15 13:48:23,582 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 13:48:23,582 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 27 [2022-04-15 13:48:23,582 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 13:48:23,582 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-15 13:48:23,583 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-15 13:48:23,584 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-15 13:48:23,585 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-15 13:48:23,585 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 67 transitions. [2022-04-15 13:48:23,653 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 67 edges. 67 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:23,654 INFO L225 Difference]: With dead ends: 62 [2022-04-15 13:48:23,654 INFO L226 Difference]: Without dead ends: 50 [2022-04-15 13:48:23,654 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-15 13:48:23,655 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 6 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-15 13:48:23,655 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 130 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-15 13:48:23,655 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-04-15 13:48:23,670 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2022-04-15 13:48:23,670 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 13:48:23,670 INFO L82 GeneralOperation]: Start isEquivalent. First operand 50 states. Second operand has 50 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-15 13:48:23,671 INFO L74 IsIncluded]: Start isIncluded. First operand 50 states. Second operand has 50 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-15 13:48:23,671 INFO L87 Difference]: Start difference. First operand 50 states. Second operand has 50 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-15 13:48:23,672 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:23,672 INFO L93 Difference]: Finished difference Result 50 states and 62 transitions. [2022-04-15 13:48:23,672 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 62 transitions. [2022-04-15 13:48:23,673 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 13:48:23,673 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 13:48:23,673 INFO L74 IsIncluded]: Start isIncluded. First operand has 50 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) Second operand 50 states. [2022-04-15 13:48:23,673 INFO L87 Difference]: Start difference. First operand has 50 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) Second operand 50 states. [2022-04-15 13:48:23,674 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 13:48:23,675 INFO L93 Difference]: Finished difference Result 50 states and 62 transitions. [2022-04-15 13:48:23,675 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 62 transitions. [2022-04-15 13:48:23,675 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 13:48:23,675 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 13:48:23,675 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 13:48:23,675 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 13:48:23,675 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 25 states have (on average 1.12) internal successors, (28), 26 states have internal predecessors, (28), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-15 13:48:23,676 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 62 transitions. [2022-04-15 13:48:23,677 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 62 transitions. Word has length 27 [2022-04-15 13:48:23,677 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 13:48:23,677 INFO L478 AbstractCegarLoop]: Abstraction has 50 states and 62 transitions. [2022-04-15 13:48:23,677 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-15 13:48:23,677 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 50 states and 62 transitions. [2022-04-15 13:48:23,732 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 62 edges. 62 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 13:48:23,732 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 62 transitions. [2022-04-15 13:48:23,732 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-04-15 13:48:23,732 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 13:48:23,733 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 13:48:23,748 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-15 13:48:23,935 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 13:48:23,936 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 13:48:23,936 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 13:48:23,936 INFO L85 PathProgramCache]: Analyzing trace with hash 1440923632, now seen corresponding path program 1 times [2022-04-15 13:48:23,936 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 13:48:23,936 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [489602491]