/usr/bin/java -ea -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/geo3-ll_valuebound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-08 06:15:51,271 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-08 06:15:51,273 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-08 06:15:51,300 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-08 06:15:51,300 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-08 06:15:51,301 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-08 06:15:51,302 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-08 06:15:51,304 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-08 06:15:51,307 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-08 06:15:51,310 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-08 06:15:51,311 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-08 06:15:51,312 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-08 06:15:51,312 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-08 06:15:51,314 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-08 06:15:51,314 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-08 06:15:51,316 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-08 06:15:51,316 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-08 06:15:51,317 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-08 06:15:51,321 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-08 06:15:51,325 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-08 06:15:51,326 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-08 06:15:51,327 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-08 06:15:51,327 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-08 06:15:51,329 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-08 06:15:51,330 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-08 06:15:51,335 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-08 06:15:51,335 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-08 06:15:51,335 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-08 06:15:51,335 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-08 06:15:51,336 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-08 06:15:51,337 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-08 06:15:51,337 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-08 06:15:51,338 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-08 06:15:51,338 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-08 06:15:51,339 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-08 06:15:51,339 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-08 06:15:51,339 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-08 06:15:51,340 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-08 06:15:51,340 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-08 06:15:51,340 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-08 06:15:51,340 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-08 06:15:51,341 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-08 06:15:51,342 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-04-08 06:15:51,350 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-08 06:15:51,350 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-08 06:15:51,352 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-08 06:15:51,352 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-08 06:15:51,352 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-08 06:15:51,352 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-08 06:15:51,352 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-08 06:15:51,352 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-08 06:15:51,352 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-08 06:15:51,353 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-08 06:15:51,353 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-08 06:15:51,353 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-08 06:15:51,353 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-08 06:15:51,353 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-08 06:15:51,353 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-08 06:15:51,353 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-08 06:15:51,353 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-08 06:15:51,353 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-08 06:15:51,353 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 06:15:51,353 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-08 06:15:51,354 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-08 06:15:51,354 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-08 06:15:51,354 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-08 06:15:51,354 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-08 06:15:51,354 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-08 06:15:51,354 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-08 06:15:51,515 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-08 06:15:51,538 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-08 06:15:51,539 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-08 06:15:51,540 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-08 06:15:51,541 INFO L275 PluginConnector]: CDTParser initialized [2022-04-08 06:15:51,542 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/geo3-ll_valuebound100.c [2022-04-08 06:15:51,590 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5ef1bf114/6dbe649ccad64b15b57d46462b27c452/FLAG7331fe619 [2022-04-08 06:15:51,962 INFO L306 CDTParser]: Found 1 translation units. [2022-04-08 06:15:51,962 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/geo3-ll_valuebound100.c [2022-04-08 06:15:51,967 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5ef1bf114/6dbe649ccad64b15b57d46462b27c452/FLAG7331fe619 [2022-04-08 06:15:51,979 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5ef1bf114/6dbe649ccad64b15b57d46462b27c452 [2022-04-08 06:15:51,981 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-08 06:15:51,982 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-08 06:15:51,985 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-08 06:15:51,985 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-08 06:15:51,987 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-08 06:15:51,991 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 06:15:51" (1/1) ... [2022-04-08 06:15:51,992 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@60910bac and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:15:51, skipping insertion in model container [2022-04-08 06:15:51,992 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 06:15:51" (1/1) ... [2022-04-08 06:15:51,997 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-08 06:15:52,007 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-08 06:15:52,153 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/geo3-ll_valuebound100.c[525,538] [2022-04-08 06:15:52,176 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 06:15:52,182 INFO L203 MainTranslator]: Completed pre-run [2022-04-08 06:15:52,192 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/geo3-ll_valuebound100.c[525,538] [2022-04-08 06:15:52,210 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 06:15:52,218 INFO L208 MainTranslator]: Completed translation [2022-04-08 06:15:52,219 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:15:52 WrapperNode [2022-04-08 06:15:52,219 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-08 06:15:52,219 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-08 06:15:52,220 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-08 06:15:52,220 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-08 06:15:52,227 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:15:52" (1/1) ... [2022-04-08 06:15:52,227 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:15:52" (1/1) ... [2022-04-08 06:15:52,232 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:15:52" (1/1) ... [2022-04-08 06:15:52,233 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:15:52" (1/1) ... [2022-04-08 06:15:52,242 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:15:52" (1/1) ... [2022-04-08 06:15:52,246 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:15:52" (1/1) ... [2022-04-08 06:15:52,250 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:15:52" (1/1) ... [2022-04-08 06:15:52,252 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-08 06:15:52,253 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-08 06:15:52,253 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-08 06:15:52,253 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-08 06:15:52,253 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:15:52" (1/1) ... [2022-04-08 06:15:52,258 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 06:15:52,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 06:15:52,276 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-08 06:15:52,299 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-08 06:15:52,308 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-08 06:15:52,308 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-08 06:15:52,309 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-08 06:15:52,309 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-08 06:15:52,309 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-08 06:15:52,309 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-08 06:15:52,309 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-08 06:15:52,309 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-08 06:15:52,310 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-08 06:15:52,310 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-08 06:15:52,310 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-08 06:15:52,310 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-08 06:15:52,311 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-08 06:15:52,311 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-08 06:15:52,311 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-08 06:15:52,311 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-08 06:15:52,311 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-08 06:15:52,311 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-08 06:15:52,311 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-08 06:15:52,311 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-08 06:15:52,358 INFO L234 CfgBuilder]: Building ICFG [2022-04-08 06:15:52,360 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-08 06:15:52,526 INFO L275 CfgBuilder]: Performing block encoding [2022-04-08 06:15:52,531 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-08 06:15:52,531 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-08 06:15:52,532 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 06:15:52 BoogieIcfgContainer [2022-04-08 06:15:52,532 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-08 06:15:52,533 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-08 06:15:52,534 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-08 06:15:52,549 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-08 06:15:52,550 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.04 06:15:51" (1/3) ... [2022-04-08 06:15:52,550 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3698ca73 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 06:15:52, skipping insertion in model container [2022-04-08 06:15:52,550 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 06:15:52" (2/3) ... [2022-04-08 06:15:52,550 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3698ca73 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 06:15:52, skipping insertion in model container [2022-04-08 06:15:52,550 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 06:15:52" (3/3) ... [2022-04-08 06:15:52,551 INFO L111 eAbstractionObserver]: Analyzing ICFG geo3-ll_valuebound100.c [2022-04-08 06:15:52,555 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-08 06:15:52,555 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-08 06:15:52,581 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-08 06:15:52,585 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-08 06:15:52,585 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-08 06:15:52,618 INFO L276 IsEmpty]: Start isEmpty. Operand has 31 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:15:52,623 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-04-08 06:15:52,623 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:15:52,623 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:15:52,624 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:15:52,627 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:15:52,627 INFO L85 PathProgramCache]: Analyzing trace with hash -779299010, now seen corresponding path program 1 times [2022-04-08 06:15:52,636 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:15:52,637 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1815697895] [2022-04-08 06:15:52,647 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 06:15:52,647 INFO L85 PathProgramCache]: Analyzing trace with hash -779299010, now seen corresponding path program 2 times [2022-04-08 06:15:52,649 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:15:52,650 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [881465756] [2022-04-08 06:15:52,650 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:15:52,651 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:15:52,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:15:52,764 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 06:15:52,777 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:15:52,794 INFO L290 TraceCheckUtils]: 0: Hoare triple {51#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3); {34#true} is VALID [2022-04-08 06:15:52,795 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-08 06:15:52,795 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {34#true} {34#true} #65#return; {34#true} is VALID [2022-04-08 06:15:52,795 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-08 06:15:52,797 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:15:52,801 INFO L290 TraceCheckUtils]: 0: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-08 06:15:52,802 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-08 06:15:52,802 INFO L290 TraceCheckUtils]: 2: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-08 06:15:52,802 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {35#false} {34#true} #55#return; {35#false} is VALID [2022-04-08 06:15:52,802 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-08 06:15:52,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:15:52,808 INFO L290 TraceCheckUtils]: 0: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-08 06:15:52,808 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-08 06:15:52,808 INFO L290 TraceCheckUtils]: 2: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-08 06:15:52,808 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {35#false} {35#false} #57#return; {35#false} is VALID [2022-04-08 06:15:52,809 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2022-04-08 06:15:52,810 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:15:52,814 INFO L290 TraceCheckUtils]: 0: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-08 06:15:52,814 INFO L290 TraceCheckUtils]: 1: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-08 06:15:52,814 INFO L290 TraceCheckUtils]: 2: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-08 06:15:52,814 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {35#false} {35#false} #59#return; {35#false} is VALID [2022-04-08 06:15:52,820 INFO L272 TraceCheckUtils]: 0: Hoare triple {34#true} call ULTIMATE.init(); {51#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 06:15:52,820 INFO L290 TraceCheckUtils]: 1: Hoare triple {51#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3); {34#true} is VALID [2022-04-08 06:15:52,820 INFO L290 TraceCheckUtils]: 2: Hoare triple {34#true} assume true; {34#true} is VALID [2022-04-08 06:15:52,821 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {34#true} {34#true} #65#return; {34#true} is VALID [2022-04-08 06:15:52,821 INFO L272 TraceCheckUtils]: 4: Hoare triple {34#true} call #t~ret7 := main(); {34#true} is VALID [2022-04-08 06:15:52,821 INFO L290 TraceCheckUtils]: 5: Hoare triple {34#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {34#true} is VALID [2022-04-08 06:15:52,821 INFO L272 TraceCheckUtils]: 6: Hoare triple {34#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 100 then 1 else 0)); {34#true} is VALID [2022-04-08 06:15:52,822 INFO L290 TraceCheckUtils]: 7: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-08 06:15:52,823 INFO L290 TraceCheckUtils]: 8: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-08 06:15:52,824 INFO L290 TraceCheckUtils]: 9: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-08 06:15:52,824 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {35#false} {34#true} #55#return; {35#false} is VALID [2022-04-08 06:15:52,824 INFO L290 TraceCheckUtils]: 11: Hoare triple {35#false} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {35#false} is VALID [2022-04-08 06:15:52,824 INFO L272 TraceCheckUtils]: 12: Hoare triple {35#false} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 100 then 1 else 0)); {34#true} is VALID [2022-04-08 06:15:52,824 INFO L290 TraceCheckUtils]: 13: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-08 06:15:52,825 INFO L290 TraceCheckUtils]: 14: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-08 06:15:52,825 INFO L290 TraceCheckUtils]: 15: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-08 06:15:52,826 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {35#false} {35#false} #57#return; {35#false} is VALID [2022-04-08 06:15:52,826 INFO L290 TraceCheckUtils]: 17: Hoare triple {35#false} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {35#false} is VALID [2022-04-08 06:15:52,826 INFO L272 TraceCheckUtils]: 18: Hoare triple {35#false} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 100 then 1 else 0)); {34#true} is VALID [2022-04-08 06:15:52,827 INFO L290 TraceCheckUtils]: 19: Hoare triple {34#true} ~cond := #in~cond; {34#true} is VALID [2022-04-08 06:15:52,827 INFO L290 TraceCheckUtils]: 20: Hoare triple {34#true} assume 0 == ~cond;assume false; {35#false} is VALID [2022-04-08 06:15:52,827 INFO L290 TraceCheckUtils]: 21: Hoare triple {35#false} assume true; {35#false} is VALID [2022-04-08 06:15:52,828 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {35#false} {35#false} #59#return; {35#false} is VALID [2022-04-08 06:15:52,828 INFO L290 TraceCheckUtils]: 23: Hoare triple {35#false} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {35#false} is VALID [2022-04-08 06:15:52,828 INFO L290 TraceCheckUtils]: 24: Hoare triple {35#false} assume !true; {35#false} is VALID [2022-04-08 06:15:52,828 INFO L272 TraceCheckUtils]: 25: Hoare triple {35#false} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {35#false} is VALID [2022-04-08 06:15:52,828 INFO L290 TraceCheckUtils]: 26: Hoare triple {35#false} ~cond := #in~cond; {35#false} is VALID [2022-04-08 06:15:52,828 INFO L290 TraceCheckUtils]: 27: Hoare triple {35#false} assume 0 == ~cond; {35#false} is VALID [2022-04-08 06:15:52,829 INFO L290 TraceCheckUtils]: 28: Hoare triple {35#false} assume !false; {35#false} is VALID [2022-04-08 06:15:52,829 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-08 06:15:52,829 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:15:52,829 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [881465756] [2022-04-08 06:15:52,830 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [881465756] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:15:52,830 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:15:52,830 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 06:15:52,832 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:15:52,832 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1815697895] [2022-04-08 06:15:52,832 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1815697895] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:15:52,832 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:15:52,832 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 06:15:52,832 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1745235047] [2022-04-08 06:15:52,833 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:15:52,836 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2022-04-08 06:15:52,838 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:15:52,840 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:15:52,878 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 23 edges. 23 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:15:52,878 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-08 06:15:52,878 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:15:52,895 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-08 06:15:52,895 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-08 06:15:52,897 INFO L87 Difference]: Start difference. First operand has 31 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 7 states have call successors, (7), 4 states have call predecessors, (7), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:15:53,015 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:15:53,015 INFO L93 Difference]: Finished difference Result 55 states and 73 transitions. [2022-04-08 06:15:53,015 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-08 06:15:53,016 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2022-04-08 06:15:53,016 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:15:53,017 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:15:53,022 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 73 transitions. [2022-04-08 06:15:53,022 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:15:53,026 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 73 transitions. [2022-04-08 06:15:53,026 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 73 transitions. [2022-04-08 06:15:53,091 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 73 edges. 73 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:15:53,098 INFO L225 Difference]: With dead ends: 55 [2022-04-08 06:15:53,098 INFO L226 Difference]: Without dead ends: 26 [2022-04-08 06:15:53,113 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-08 06:15:53,116 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 17 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 06:15:53,117 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 32 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 06:15:53,128 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2022-04-08 06:15:53,143 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2022-04-08 06:15:53,144 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:15:53,145 INFO L82 GeneralOperation]: Start isEquivalent. First operand 26 states. Second operand has 26 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-08 06:15:53,145 INFO L74 IsIncluded]: Start isIncluded. First operand 26 states. Second operand has 26 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-08 06:15:53,146 INFO L87 Difference]: Start difference. First operand 26 states. Second operand has 26 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-08 06:15:53,151 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:15:53,151 INFO L93 Difference]: Finished difference Result 26 states and 29 transitions. [2022-04-08 06:15:53,151 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2022-04-08 06:15:53,152 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:15:53,152 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:15:53,153 INFO L74 IsIncluded]: Start isIncluded. First operand has 26 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand 26 states. [2022-04-08 06:15:53,153 INFO L87 Difference]: Start difference. First operand has 26 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Second operand 26 states. [2022-04-08 06:15:53,158 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:15:53,158 INFO L93 Difference]: Finished difference Result 26 states and 29 transitions. [2022-04-08 06:15:53,158 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2022-04-08 06:15:53,158 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:15:53,159 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:15:53,159 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:15:53,159 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:15:53,160 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 16 states have internal predecessors, (17), 7 states have call successors, (7), 4 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-08 06:15:53,163 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2022-04-08 06:15:53,164 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 29 [2022-04-08 06:15:53,164 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:15:53,164 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2022-04-08 06:15:53,165 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.333333333333333) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-08 06:15:53,165 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 26 states and 29 transitions. [2022-04-08 06:15:53,194 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 29 edges. 29 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:15:53,195 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2022-04-08 06:15:53,196 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-04-08 06:15:53,196 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:15:53,196 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:15:53,196 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-08 06:15:53,197 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:15:53,198 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:15:53,199 INFO L85 PathProgramCache]: Analyzing trace with hash -963850242, now seen corresponding path program 1 times [2022-04-08 06:15:53,199 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:15:53,199 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1815784042] [2022-04-08 06:15:53,201 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 06:15:53,202 INFO L85 PathProgramCache]: Analyzing trace with hash -963850242, now seen corresponding path program 2 times [2022-04-08 06:15:53,202 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:15:53,202 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1942762283] [2022-04-08 06:15:53,202 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:15:53,203 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:15:53,244 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 06:15:53,244 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1207898471] [2022-04-08 06:15:53,244 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 06:15:53,244 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:15:53,245 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 06:15:53,250 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 06:15:53,251 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-08 06:15:53,297 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 06:15:53,297 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 06:15:53,309 INFO L263 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-08 06:15:53,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:15:53,324 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 06:15:53,539 INFO L272 TraceCheckUtils]: 0: Hoare triple {268#true} call ULTIMATE.init(); {268#true} is VALID [2022-04-08 06:15:53,540 INFO L290 TraceCheckUtils]: 1: Hoare triple {268#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3); {268#true} is VALID [2022-04-08 06:15:53,540 INFO L290 TraceCheckUtils]: 2: Hoare triple {268#true} assume true; {268#true} is VALID [2022-04-08 06:15:53,540 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {268#true} {268#true} #65#return; {268#true} is VALID [2022-04-08 06:15:53,543 INFO L272 TraceCheckUtils]: 4: Hoare triple {268#true} call #t~ret7 := main(); {268#true} is VALID [2022-04-08 06:15:53,543 INFO L290 TraceCheckUtils]: 5: Hoare triple {268#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {268#true} is VALID [2022-04-08 06:15:53,544 INFO L272 TraceCheckUtils]: 6: Hoare triple {268#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 100 then 1 else 0)); {268#true} is VALID [2022-04-08 06:15:53,544 INFO L290 TraceCheckUtils]: 7: Hoare triple {268#true} ~cond := #in~cond; {268#true} is VALID [2022-04-08 06:15:53,544 INFO L290 TraceCheckUtils]: 8: Hoare triple {268#true} assume !(0 == ~cond); {268#true} is VALID [2022-04-08 06:15:53,545 INFO L290 TraceCheckUtils]: 9: Hoare triple {268#true} assume true; {268#true} is VALID [2022-04-08 06:15:53,545 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {268#true} {268#true} #55#return; {268#true} is VALID [2022-04-08 06:15:53,546 INFO L290 TraceCheckUtils]: 11: Hoare triple {268#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {268#true} is VALID [2022-04-08 06:15:53,547 INFO L272 TraceCheckUtils]: 12: Hoare triple {268#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 100 then 1 else 0)); {268#true} is VALID [2022-04-08 06:15:53,547 INFO L290 TraceCheckUtils]: 13: Hoare triple {268#true} ~cond := #in~cond; {268#true} is VALID [2022-04-08 06:15:53,547 INFO L290 TraceCheckUtils]: 14: Hoare triple {268#true} assume !(0 == ~cond); {268#true} is VALID [2022-04-08 06:15:53,548 INFO L290 TraceCheckUtils]: 15: Hoare triple {268#true} assume true; {268#true} is VALID [2022-04-08 06:15:53,548 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {268#true} {268#true} #57#return; {268#true} is VALID [2022-04-08 06:15:53,548 INFO L290 TraceCheckUtils]: 17: Hoare triple {268#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {268#true} is VALID [2022-04-08 06:15:53,548 INFO L272 TraceCheckUtils]: 18: Hoare triple {268#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 100 then 1 else 0)); {268#true} is VALID [2022-04-08 06:15:53,548 INFO L290 TraceCheckUtils]: 19: Hoare triple {268#true} ~cond := #in~cond; {268#true} is VALID [2022-04-08 06:15:53,548 INFO L290 TraceCheckUtils]: 20: Hoare triple {268#true} assume !(0 == ~cond); {268#true} is VALID [2022-04-08 06:15:53,548 INFO L290 TraceCheckUtils]: 21: Hoare triple {268#true} assume true; {268#true} is VALID [2022-04-08 06:15:53,549 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {268#true} {268#true} #59#return; {268#true} is VALID [2022-04-08 06:15:53,549 INFO L290 TraceCheckUtils]: 23: Hoare triple {268#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {342#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:15:53,550 INFO L290 TraceCheckUtils]: 24: Hoare triple {342#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {342#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:15:53,551 INFO L272 TraceCheckUtils]: 25: Hoare triple {342#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {349#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 06:15:53,552 INFO L290 TraceCheckUtils]: 26: Hoare triple {349#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {353#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:15:53,552 INFO L290 TraceCheckUtils]: 27: Hoare triple {353#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {269#false} is VALID [2022-04-08 06:15:53,552 INFO L290 TraceCheckUtils]: 28: Hoare triple {269#false} assume !false; {269#false} is VALID [2022-04-08 06:15:53,553 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-08 06:15:53,553 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 06:15:53,553 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:15:53,554 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1942762283] [2022-04-08 06:15:53,554 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 06:15:53,554 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1207898471] [2022-04-08 06:15:53,555 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1207898471] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:15:53,555 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:15:53,555 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 06:15:53,556 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:15:53,557 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1815784042] [2022-04-08 06:15:53,557 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1815784042] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:15:53,557 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:15:53,557 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 06:15:53,557 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [890694384] [2022-04-08 06:15:53,557 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:15:53,558 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2022-04-08 06:15:53,559 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:15:53,560 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-08 06:15:53,578 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 23 edges. 23 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:15:53,579 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 06:15:53,579 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:15:53,579 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 06:15:53,580 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-08 06:15:53,580 INFO L87 Difference]: Start difference. First operand 26 states and 29 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-08 06:15:53,706 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:15:53,706 INFO L93 Difference]: Finished difference Result 36 states and 40 transitions. [2022-04-08 06:15:53,706 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 06:15:53,707 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2022-04-08 06:15:53,707 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:15:53,707 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-08 06:15:53,709 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 40 transitions. [2022-04-08 06:15:53,709 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-08 06:15:53,710 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 40 transitions. [2022-04-08 06:15:53,710 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 40 transitions. [2022-04-08 06:15:53,743 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 40 edges. 40 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:15:53,750 INFO L225 Difference]: With dead ends: 36 [2022-04-08 06:15:53,750 INFO L226 Difference]: Without dead ends: 33 [2022-04-08 06:15:53,751 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-08 06:15:53,752 INFO L913 BasicCegarLoop]: 26 mSDtfsCounter, 6 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 06:15:53,756 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 93 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 06:15:53,758 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-04-08 06:15:53,768 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-04-08 06:15:53,768 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:15:53,768 INFO L82 GeneralOperation]: Start isEquivalent. First operand 33 states. Second operand has 33 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-08 06:15:53,768 INFO L74 IsIncluded]: Start isIncluded. First operand 33 states. Second operand has 33 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-08 06:15:53,769 INFO L87 Difference]: Start difference. First operand 33 states. Second operand has 33 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-08 06:15:53,773 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:15:53,773 INFO L93 Difference]: Finished difference Result 33 states and 36 transitions. [2022-04-08 06:15:53,773 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 36 transitions. [2022-04-08 06:15:53,774 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:15:53,774 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:15:53,776 INFO L74 IsIncluded]: Start isIncluded. First operand has 33 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand 33 states. [2022-04-08 06:15:53,777 INFO L87 Difference]: Start difference. First operand has 33 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand 33 states. [2022-04-08 06:15:53,779 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:15:53,779 INFO L93 Difference]: Finished difference Result 33 states and 36 transitions. [2022-04-08 06:15:53,779 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 36 transitions. [2022-04-08 06:15:53,779 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:15:53,779 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:15:53,780 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:15:53,780 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:15:53,780 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 20 states have (on average 1.1) internal successors, (22), 21 states have internal predecessors, (22), 8 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-08 06:15:53,787 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 36 transitions. [2022-04-08 06:15:53,787 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 36 transitions. Word has length 29 [2022-04-08 06:15:53,787 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:15:53,787 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 36 transitions. [2022-04-08 06:15:53,787 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-08 06:15:53,787 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 33 states and 36 transitions. [2022-04-08 06:15:53,825 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 36 edges. 36 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:15:53,825 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 36 transitions. [2022-04-08 06:15:53,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-08 06:15:53,830 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:15:53,830 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:15:53,849 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-04-08 06:15:54,046 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:15:54,047 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:15:54,047 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:15:54,047 INFO L85 PathProgramCache]: Analyzing trace with hash -425626518, now seen corresponding path program 1 times [2022-04-08 06:15:54,047 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:15:54,048 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1690892050] [2022-04-08 06:15:54,048 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 06:15:54,048 INFO L85 PathProgramCache]: Analyzing trace with hash -425626518, now seen corresponding path program 2 times [2022-04-08 06:15:54,048 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:15:54,048 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [278521708] [2022-04-08 06:15:54,048 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:15:54,049 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:15:54,083 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 06:15:54,083 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1800609167] [2022-04-08 06:15:54,083 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 06:15:54,083 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:15:54,083 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 06:15:54,099 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 06:15:54,100 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-08 06:15:54,146 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-08 06:15:54,146 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 06:15:54,147 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 25 conjunts are in the unsatisfiable core [2022-04-08 06:15:54,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:15:54,163 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 06:15:54,457 INFO L272 TraceCheckUtils]: 0: Hoare triple {565#true} call ULTIMATE.init(); {565#true} is VALID [2022-04-08 06:15:54,457 INFO L290 TraceCheckUtils]: 1: Hoare triple {565#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3); {565#true} is VALID [2022-04-08 06:15:54,458 INFO L290 TraceCheckUtils]: 2: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-08 06:15:54,458 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {565#true} {565#true} #65#return; {565#true} is VALID [2022-04-08 06:15:54,458 INFO L272 TraceCheckUtils]: 4: Hoare triple {565#true} call #t~ret7 := main(); {565#true} is VALID [2022-04-08 06:15:54,458 INFO L290 TraceCheckUtils]: 5: Hoare triple {565#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {565#true} is VALID [2022-04-08 06:15:54,458 INFO L272 TraceCheckUtils]: 6: Hoare triple {565#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 100 then 1 else 0)); {565#true} is VALID [2022-04-08 06:15:54,458 INFO L290 TraceCheckUtils]: 7: Hoare triple {565#true} ~cond := #in~cond; {565#true} is VALID [2022-04-08 06:15:54,458 INFO L290 TraceCheckUtils]: 8: Hoare triple {565#true} assume !(0 == ~cond); {565#true} is VALID [2022-04-08 06:15:54,458 INFO L290 TraceCheckUtils]: 9: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-08 06:15:54,459 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {565#true} {565#true} #55#return; {565#true} is VALID [2022-04-08 06:15:54,459 INFO L290 TraceCheckUtils]: 11: Hoare triple {565#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {565#true} is VALID [2022-04-08 06:15:54,459 INFO L272 TraceCheckUtils]: 12: Hoare triple {565#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 100 then 1 else 0)); {565#true} is VALID [2022-04-08 06:15:54,459 INFO L290 TraceCheckUtils]: 13: Hoare triple {565#true} ~cond := #in~cond; {565#true} is VALID [2022-04-08 06:15:54,459 INFO L290 TraceCheckUtils]: 14: Hoare triple {565#true} assume !(0 == ~cond); {565#true} is VALID [2022-04-08 06:15:54,459 INFO L290 TraceCheckUtils]: 15: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-08 06:15:54,459 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {565#true} {565#true} #57#return; {565#true} is VALID [2022-04-08 06:15:54,459 INFO L290 TraceCheckUtils]: 17: Hoare triple {565#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {565#true} is VALID [2022-04-08 06:15:54,460 INFO L272 TraceCheckUtils]: 18: Hoare triple {565#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 100 then 1 else 0)); {565#true} is VALID [2022-04-08 06:15:54,461 INFO L290 TraceCheckUtils]: 19: Hoare triple {565#true} ~cond := #in~cond; {627#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} is VALID [2022-04-08 06:15:54,461 INFO L290 TraceCheckUtils]: 20: Hoare triple {627#(= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)} assume !(0 == ~cond); {631#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-08 06:15:54,461 INFO L290 TraceCheckUtils]: 21: Hoare triple {631#(not (= |assume_abort_if_not_#in~cond| 0))} assume true; {631#(not (= |assume_abort_if_not_#in~cond| 0))} is VALID [2022-04-08 06:15:54,462 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {631#(not (= |assume_abort_if_not_#in~cond| 0))} {565#true} #59#return; {565#true} is VALID [2022-04-08 06:15:54,463 INFO L290 TraceCheckUtils]: 23: Hoare triple {565#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:15:54,464 INFO L290 TraceCheckUtils]: 24: Hoare triple {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:15:54,464 INFO L272 TraceCheckUtils]: 25: Hoare triple {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {565#true} is VALID [2022-04-08 06:15:54,464 INFO L290 TraceCheckUtils]: 26: Hoare triple {565#true} ~cond := #in~cond; {651#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:15:54,465 INFO L290 TraceCheckUtils]: 27: Hoare triple {651#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {655#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:15:54,465 INFO L290 TraceCheckUtils]: 28: Hoare triple {655#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {655#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:15:54,472 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {655#(not (= |__VERIFIER_assert_#in~cond| 0))} {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} #61#return; {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:15:54,473 INFO L290 TraceCheckUtils]: 30: Hoare triple {641#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {665#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:15:54,473 INFO L290 TraceCheckUtils]: 31: Hoare triple {665#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {665#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:15:54,479 INFO L272 TraceCheckUtils]: 32: Hoare triple {665#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {672#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 06:15:54,479 INFO L290 TraceCheckUtils]: 33: Hoare triple {672#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {676#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:15:54,480 INFO L290 TraceCheckUtils]: 34: Hoare triple {676#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {566#false} is VALID [2022-04-08 06:15:54,480 INFO L290 TraceCheckUtils]: 35: Hoare triple {566#false} assume !false; {566#false} is VALID [2022-04-08 06:15:54,480 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 7 proven. 3 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-04-08 06:15:54,481 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-08 06:16:01,050 INFO L290 TraceCheckUtils]: 35: Hoare triple {566#false} assume !false; {566#false} is VALID [2022-04-08 06:16:01,051 INFO L290 TraceCheckUtils]: 34: Hoare triple {676#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {566#false} is VALID [2022-04-08 06:16:01,054 INFO L290 TraceCheckUtils]: 33: Hoare triple {672#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {676#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:16:01,055 INFO L272 TraceCheckUtils]: 32: Hoare triple {692#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {672#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 06:16:01,056 INFO L290 TraceCheckUtils]: 31: Hoare triple {692#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} assume !false; {692#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} is VALID [2022-04-08 06:16:01,126 INFO L290 TraceCheckUtils]: 30: Hoare triple {699#(= (+ (* main_~z~0 main_~x~0) main_~a~0 (* main_~az~0 (* main_~z~0 main_~y~0))) (+ main_~a~0 (* main_~z~0 (+ (* main_~z~0 main_~x~0) main_~a~0))))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {692#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} is VALID [2022-04-08 06:16:01,130 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {655#(not (= |__VERIFIER_assert_#in~cond| 0))} {565#true} #61#return; {699#(= (+ (* main_~z~0 main_~x~0) main_~a~0 (* main_~az~0 (* main_~z~0 main_~y~0))) (+ main_~a~0 (* main_~z~0 (+ (* main_~z~0 main_~x~0) main_~a~0))))} is VALID [2022-04-08 06:16:01,131 INFO L290 TraceCheckUtils]: 28: Hoare triple {655#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {655#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:16:01,131 INFO L290 TraceCheckUtils]: 27: Hoare triple {712#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {655#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:16:01,133 INFO L290 TraceCheckUtils]: 26: Hoare triple {565#true} ~cond := #in~cond; {712#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 06:16:01,133 INFO L272 TraceCheckUtils]: 25: Hoare triple {565#true} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {565#true} is VALID [2022-04-08 06:16:01,133 INFO L290 TraceCheckUtils]: 24: Hoare triple {565#true} assume !false; {565#true} is VALID [2022-04-08 06:16:01,133 INFO L290 TraceCheckUtils]: 23: Hoare triple {565#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {565#true} is VALID [2022-04-08 06:16:01,133 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {565#true} {565#true} #59#return; {565#true} is VALID [2022-04-08 06:16:01,134 INFO L290 TraceCheckUtils]: 21: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-08 06:16:01,134 INFO L290 TraceCheckUtils]: 20: Hoare triple {565#true} assume !(0 == ~cond); {565#true} is VALID [2022-04-08 06:16:01,134 INFO L290 TraceCheckUtils]: 19: Hoare triple {565#true} ~cond := #in~cond; {565#true} is VALID [2022-04-08 06:16:01,134 INFO L272 TraceCheckUtils]: 18: Hoare triple {565#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 100 then 1 else 0)); {565#true} is VALID [2022-04-08 06:16:01,134 INFO L290 TraceCheckUtils]: 17: Hoare triple {565#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {565#true} is VALID [2022-04-08 06:16:01,134 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {565#true} {565#true} #57#return; {565#true} is VALID [2022-04-08 06:16:01,134 INFO L290 TraceCheckUtils]: 15: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-08 06:16:01,134 INFO L290 TraceCheckUtils]: 14: Hoare triple {565#true} assume !(0 == ~cond); {565#true} is VALID [2022-04-08 06:16:01,135 INFO L290 TraceCheckUtils]: 13: Hoare triple {565#true} ~cond := #in~cond; {565#true} is VALID [2022-04-08 06:16:01,135 INFO L272 TraceCheckUtils]: 12: Hoare triple {565#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 100 then 1 else 0)); {565#true} is VALID [2022-04-08 06:16:01,135 INFO L290 TraceCheckUtils]: 11: Hoare triple {565#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {565#true} is VALID [2022-04-08 06:16:01,135 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {565#true} {565#true} #55#return; {565#true} is VALID [2022-04-08 06:16:01,135 INFO L290 TraceCheckUtils]: 9: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-08 06:16:01,135 INFO L290 TraceCheckUtils]: 8: Hoare triple {565#true} assume !(0 == ~cond); {565#true} is VALID [2022-04-08 06:16:01,135 INFO L290 TraceCheckUtils]: 7: Hoare triple {565#true} ~cond := #in~cond; {565#true} is VALID [2022-04-08 06:16:01,135 INFO L272 TraceCheckUtils]: 6: Hoare triple {565#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 100 then 1 else 0)); {565#true} is VALID [2022-04-08 06:16:01,136 INFO L290 TraceCheckUtils]: 5: Hoare triple {565#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {565#true} is VALID [2022-04-08 06:16:01,136 INFO L272 TraceCheckUtils]: 4: Hoare triple {565#true} call #t~ret7 := main(); {565#true} is VALID [2022-04-08 06:16:01,136 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {565#true} {565#true} #65#return; {565#true} is VALID [2022-04-08 06:16:01,136 INFO L290 TraceCheckUtils]: 2: Hoare triple {565#true} assume true; {565#true} is VALID [2022-04-08 06:16:01,136 INFO L290 TraceCheckUtils]: 1: Hoare triple {565#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3); {565#true} is VALID [2022-04-08 06:16:01,136 INFO L272 TraceCheckUtils]: 0: Hoare triple {565#true} call ULTIMATE.init(); {565#true} is VALID [2022-04-08 06:16:01,136 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-08 06:16:01,137 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:16:01,137 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [278521708] [2022-04-08 06:16:01,137 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 06:16:01,137 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1800609167] [2022-04-08 06:16:01,137 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1800609167] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-08 06:16:01,137 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-08 06:16:01,137 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 13 [2022-04-08 06:16:01,137 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:16:01,137 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1690892050] [2022-04-08 06:16:01,138 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1690892050] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:16:01,138 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:16:01,138 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-04-08 06:16:01,138 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1807854199] [2022-04-08 06:16:01,138 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:16:01,138 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2022-04-08 06:16:01,139 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:16:01,139 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 06:16:01,234 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 33 edges. 33 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:16:01,235 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-08 06:16:01,235 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:16:01,235 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-08 06:16:01,235 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2022-04-08 06:16:01,235 INFO L87 Difference]: Start difference. First operand 33 states and 36 transitions. Second operand has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 06:16:02,624 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:16:02,624 INFO L93 Difference]: Finished difference Result 43 states and 47 transitions. [2022-04-08 06:16:02,624 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-08 06:16:02,624 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2022-04-08 06:16:02,625 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:16:02,625 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 06:16:02,626 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 44 transitions. [2022-04-08 06:16:02,626 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 06:16:02,628 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 44 transitions. [2022-04-08 06:16:02,628 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 10 states and 44 transitions. [2022-04-08 06:16:02,760 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:16:02,761 INFO L225 Difference]: With dead ends: 43 [2022-04-08 06:16:02,761 INFO L226 Difference]: Without dead ends: 40 [2022-04-08 06:16:02,762 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 59 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=49, Invalid=191, Unknown=0, NotChecked=0, Total=240 [2022-04-08 06:16:02,762 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 14 mSDsluCounter, 127 mSDsCounter, 0 mSdLazyCounter, 137 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 140 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 137 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-04-08 06:16:02,763 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [15 Valid, 149 Invalid, 140 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 137 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-04-08 06:16:02,763 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2022-04-08 06:16:02,784 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 40. [2022-04-08 06:16:02,784 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:16:02,784 INFO L82 GeneralOperation]: Start isEquivalent. First operand 40 states. Second operand has 40 states, 25 states have (on average 1.08) internal successors, (27), 26 states have internal predecessors, (27), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:16:02,785 INFO L74 IsIncluded]: Start isIncluded. First operand 40 states. Second operand has 40 states, 25 states have (on average 1.08) internal successors, (27), 26 states have internal predecessors, (27), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:16:02,791 INFO L87 Difference]: Start difference. First operand 40 states. Second operand has 40 states, 25 states have (on average 1.08) internal successors, (27), 26 states have internal predecessors, (27), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:16:02,794 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:16:02,794 INFO L93 Difference]: Finished difference Result 40 states and 43 transitions. [2022-04-08 06:16:02,794 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 43 transitions. [2022-04-08 06:16:02,794 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:16:02,794 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:16:02,795 INFO L74 IsIncluded]: Start isIncluded. First operand has 40 states, 25 states have (on average 1.08) internal successors, (27), 26 states have internal predecessors, (27), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 40 states. [2022-04-08 06:16:02,795 INFO L87 Difference]: Start difference. First operand has 40 states, 25 states have (on average 1.08) internal successors, (27), 26 states have internal predecessors, (27), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand 40 states. [2022-04-08 06:16:02,796 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:16:02,796 INFO L93 Difference]: Finished difference Result 40 states and 43 transitions. [2022-04-08 06:16:02,796 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 43 transitions. [2022-04-08 06:16:02,796 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:16:02,796 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:16:02,797 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:16:02,797 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:16:02,797 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 25 states have (on average 1.08) internal successors, (27), 26 states have internal predecessors, (27), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-08 06:16:02,798 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 43 transitions. [2022-04-08 06:16:02,798 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 43 transitions. Word has length 36 [2022-04-08 06:16:02,798 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:16:02,798 INFO L478 AbstractCegarLoop]: Abstraction has 40 states and 43 transitions. [2022-04-08 06:16:02,798 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 3 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 06:16:02,799 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 40 states and 43 transitions. [2022-04-08 06:16:02,908 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-08 06:16:02,909 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 43 transitions. [2022-04-08 06:16:02,909 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-04-08 06:16:02,909 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:16:02,910 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:16:02,971 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-08 06:16:03,110 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-04-08 06:16:03,110 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:16:03,111 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:16:03,111 INFO L85 PathProgramCache]: Analyzing trace with hash 1540046462, now seen corresponding path program 3 times [2022-04-08 06:16:03,111 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:16:03,111 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1514678305] [2022-04-08 06:16:03,111 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 06:16:03,112 INFO L85 PathProgramCache]: Analyzing trace with hash 1540046462, now seen corresponding path program 4 times [2022-04-08 06:16:03,112 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:16:03,112 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [490114690] [2022-04-08 06:16:03,112 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:16:03,112 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:16:03,153 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 06:16:03,154 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1135303073] [2022-04-08 06:16:03,155 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-08 06:16:03,155 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:16:03,155 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 06:16:03,160 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 06:16:03,174 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-08 06:16:03,241 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-08 06:16:03,241 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 06:16:03,242 INFO L263 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 27 conjunts are in the unsatisfiable core [2022-04-08 06:16:03,782 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:16:03,783 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 06:16:04,191 INFO L272 TraceCheckUtils]: 0: Hoare triple {1045#true} call ULTIMATE.init(); {1045#true} is VALID [2022-04-08 06:16:04,191 INFO L290 TraceCheckUtils]: 1: Hoare triple {1045#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3); {1045#true} is VALID [2022-04-08 06:16:04,191 INFO L290 TraceCheckUtils]: 2: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-08 06:16:04,191 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1045#true} {1045#true} #65#return; {1045#true} is VALID [2022-04-08 06:16:04,192 INFO L272 TraceCheckUtils]: 4: Hoare triple {1045#true} call #t~ret7 := main(); {1045#true} is VALID [2022-04-08 06:16:04,192 INFO L290 TraceCheckUtils]: 5: Hoare triple {1045#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {1045#true} is VALID [2022-04-08 06:16:04,192 INFO L272 TraceCheckUtils]: 6: Hoare triple {1045#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 100 then 1 else 0)); {1045#true} is VALID [2022-04-08 06:16:04,207 INFO L290 TraceCheckUtils]: 7: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-08 06:16:04,207 INFO L290 TraceCheckUtils]: 8: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-08 06:16:04,208 INFO L290 TraceCheckUtils]: 9: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-08 06:16:04,208 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1045#true} {1045#true} #55#return; {1045#true} is VALID [2022-04-08 06:16:04,208 INFO L290 TraceCheckUtils]: 11: Hoare triple {1045#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {1045#true} is VALID [2022-04-08 06:16:04,208 INFO L272 TraceCheckUtils]: 12: Hoare triple {1045#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 100 then 1 else 0)); {1045#true} is VALID [2022-04-08 06:16:04,208 INFO L290 TraceCheckUtils]: 13: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-08 06:16:04,208 INFO L290 TraceCheckUtils]: 14: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-08 06:16:04,208 INFO L290 TraceCheckUtils]: 15: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-08 06:16:04,208 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1045#true} {1045#true} #57#return; {1045#true} is VALID [2022-04-08 06:16:04,209 INFO L290 TraceCheckUtils]: 17: Hoare triple {1045#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {1045#true} is VALID [2022-04-08 06:16:04,209 INFO L272 TraceCheckUtils]: 18: Hoare triple {1045#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 100 then 1 else 0)); {1045#true} is VALID [2022-04-08 06:16:04,209 INFO L290 TraceCheckUtils]: 19: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-08 06:16:04,209 INFO L290 TraceCheckUtils]: 20: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-08 06:16:04,210 INFO L290 TraceCheckUtils]: 21: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-08 06:16:04,211 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1045#true} {1045#true} #59#return; {1045#true} is VALID [2022-04-08 06:16:04,211 INFO L290 TraceCheckUtils]: 23: Hoare triple {1045#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:16:04,212 INFO L290 TraceCheckUtils]: 24: Hoare triple {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:16:04,212 INFO L272 TraceCheckUtils]: 25: Hoare triple {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1045#true} is VALID [2022-04-08 06:16:04,212 INFO L290 TraceCheckUtils]: 26: Hoare triple {1045#true} ~cond := #in~cond; {1129#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:16:04,213 INFO L290 TraceCheckUtils]: 27: Hoare triple {1129#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:16:04,213 INFO L290 TraceCheckUtils]: 28: Hoare triple {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:16:04,214 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} #61#return; {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:16:04,215 INFO L290 TraceCheckUtils]: 30: Hoare triple {1119#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:16:04,216 INFO L290 TraceCheckUtils]: 31: Hoare triple {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:16:04,216 INFO L272 TraceCheckUtils]: 32: Hoare triple {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1045#true} is VALID [2022-04-08 06:16:04,216 INFO L290 TraceCheckUtils]: 33: Hoare triple {1045#true} ~cond := #in~cond; {1129#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:16:04,217 INFO L290 TraceCheckUtils]: 34: Hoare triple {1129#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:16:04,217 INFO L290 TraceCheckUtils]: 35: Hoare triple {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:16:04,218 INFO L284 TraceCheckUtils]: 36: Hoare quadruple {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} #61#return; {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:16:04,220 INFO L290 TraceCheckUtils]: 37: Hoare triple {1143#(and (= main_~z~0 main_~y~0) (= main_~x~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1165#(and (= main_~x~0 (+ (* main_~z~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) main_~a~0)) (= (* main_~z~0 main_~z~0) main_~y~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:16:04,220 INFO L290 TraceCheckUtils]: 38: Hoare triple {1165#(and (= main_~x~0 (+ (* main_~z~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) main_~a~0)) (= (* main_~z~0 main_~z~0) main_~y~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {1165#(and (= main_~x~0 (+ (* main_~z~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) main_~a~0)) (= (* main_~z~0 main_~z~0) main_~y~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:16:04,234 INFO L272 TraceCheckUtils]: 39: Hoare triple {1165#(and (= main_~x~0 (+ (* main_~z~0 (+ (* main_~a~0 main_~z~0) main_~a~0)) main_~a~0)) (= (* main_~z~0 main_~z~0) main_~y~0) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1172#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 06:16:04,234 INFO L290 TraceCheckUtils]: 40: Hoare triple {1172#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1176#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:16:04,235 INFO L290 TraceCheckUtils]: 41: Hoare triple {1176#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1046#false} is VALID [2022-04-08 06:16:04,235 INFO L290 TraceCheckUtils]: 42: Hoare triple {1046#false} assume !false; {1046#false} is VALID [2022-04-08 06:16:04,236 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-04-08 06:16:04,236 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-08 06:16:18,027 INFO L290 TraceCheckUtils]: 42: Hoare triple {1046#false} assume !false; {1046#false} is VALID [2022-04-08 06:16:18,028 INFO L290 TraceCheckUtils]: 41: Hoare triple {1176#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1046#false} is VALID [2022-04-08 06:16:18,028 INFO L290 TraceCheckUtils]: 40: Hoare triple {1172#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1176#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:16:18,029 INFO L272 TraceCheckUtils]: 39: Hoare triple {1192#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1172#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 06:16:18,030 INFO L290 TraceCheckUtils]: 38: Hoare triple {1192#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} assume !false; {1192#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} is VALID [2022-04-08 06:16:18,070 INFO L290 TraceCheckUtils]: 37: Hoare triple {1199#(= (+ (* main_~z~0 main_~x~0) main_~a~0 (* main_~az~0 (* main_~z~0 main_~y~0))) (+ main_~a~0 (* main_~z~0 (+ (* main_~z~0 main_~x~0) main_~a~0))))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1192#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} is VALID [2022-04-08 06:16:18,074 INFO L284 TraceCheckUtils]: 36: Hoare quadruple {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} {1045#true} #61#return; {1199#(= (+ (* main_~z~0 main_~x~0) main_~a~0 (* main_~az~0 (* main_~z~0 main_~y~0))) (+ main_~a~0 (* main_~z~0 (+ (* main_~z~0 main_~x~0) main_~a~0))))} is VALID [2022-04-08 06:16:18,074 INFO L290 TraceCheckUtils]: 35: Hoare triple {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:16:18,075 INFO L290 TraceCheckUtils]: 34: Hoare triple {1212#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {1133#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:16:18,075 INFO L290 TraceCheckUtils]: 33: Hoare triple {1045#true} ~cond := #in~cond; {1212#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 06:16:18,075 INFO L272 TraceCheckUtils]: 32: Hoare triple {1045#true} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1045#true} is VALID [2022-04-08 06:16:18,075 INFO L290 TraceCheckUtils]: 31: Hoare triple {1045#true} assume !false; {1045#true} is VALID [2022-04-08 06:16:18,075 INFO L290 TraceCheckUtils]: 30: Hoare triple {1045#true} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1045#true} is VALID [2022-04-08 06:16:18,076 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {1045#true} {1045#true} #61#return; {1045#true} is VALID [2022-04-08 06:16:18,076 INFO L290 TraceCheckUtils]: 28: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-08 06:16:18,076 INFO L290 TraceCheckUtils]: 27: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-08 06:16:18,076 INFO L290 TraceCheckUtils]: 26: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-08 06:16:18,076 INFO L272 TraceCheckUtils]: 25: Hoare triple {1045#true} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1045#true} is VALID [2022-04-08 06:16:18,076 INFO L290 TraceCheckUtils]: 24: Hoare triple {1045#true} assume !false; {1045#true} is VALID [2022-04-08 06:16:18,076 INFO L290 TraceCheckUtils]: 23: Hoare triple {1045#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {1045#true} is VALID [2022-04-08 06:16:18,076 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1045#true} {1045#true} #59#return; {1045#true} is VALID [2022-04-08 06:16:18,076 INFO L290 TraceCheckUtils]: 21: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-08 06:16:18,076 INFO L290 TraceCheckUtils]: 20: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-08 06:16:18,076 INFO L290 TraceCheckUtils]: 19: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-08 06:16:18,077 INFO L272 TraceCheckUtils]: 18: Hoare triple {1045#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 100 then 1 else 0)); {1045#true} is VALID [2022-04-08 06:16:18,077 INFO L290 TraceCheckUtils]: 17: Hoare triple {1045#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {1045#true} is VALID [2022-04-08 06:16:18,077 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1045#true} {1045#true} #57#return; {1045#true} is VALID [2022-04-08 06:16:18,077 INFO L290 TraceCheckUtils]: 15: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-08 06:16:18,077 INFO L290 TraceCheckUtils]: 14: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-08 06:16:18,077 INFO L290 TraceCheckUtils]: 13: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-08 06:16:18,077 INFO L272 TraceCheckUtils]: 12: Hoare triple {1045#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 100 then 1 else 0)); {1045#true} is VALID [2022-04-08 06:16:18,077 INFO L290 TraceCheckUtils]: 11: Hoare triple {1045#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {1045#true} is VALID [2022-04-08 06:16:18,077 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1045#true} {1045#true} #55#return; {1045#true} is VALID [2022-04-08 06:16:18,077 INFO L290 TraceCheckUtils]: 9: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-08 06:16:18,078 INFO L290 TraceCheckUtils]: 8: Hoare triple {1045#true} assume !(0 == ~cond); {1045#true} is VALID [2022-04-08 06:16:18,078 INFO L290 TraceCheckUtils]: 7: Hoare triple {1045#true} ~cond := #in~cond; {1045#true} is VALID [2022-04-08 06:16:18,078 INFO L272 TraceCheckUtils]: 6: Hoare triple {1045#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 100 then 1 else 0)); {1045#true} is VALID [2022-04-08 06:16:18,078 INFO L290 TraceCheckUtils]: 5: Hoare triple {1045#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {1045#true} is VALID [2022-04-08 06:16:18,078 INFO L272 TraceCheckUtils]: 4: Hoare triple {1045#true} call #t~ret7 := main(); {1045#true} is VALID [2022-04-08 06:16:18,078 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1045#true} {1045#true} #65#return; {1045#true} is VALID [2022-04-08 06:16:18,078 INFO L290 TraceCheckUtils]: 2: Hoare triple {1045#true} assume true; {1045#true} is VALID [2022-04-08 06:16:18,078 INFO L290 TraceCheckUtils]: 1: Hoare triple {1045#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3); {1045#true} is VALID [2022-04-08 06:16:18,078 INFO L272 TraceCheckUtils]: 0: Hoare triple {1045#true} call ULTIMATE.init(); {1045#true} is VALID [2022-04-08 06:16:18,079 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-04-08 06:16:18,079 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:16:18,079 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [490114690] [2022-04-08 06:16:18,079 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 06:16:18,079 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1135303073] [2022-04-08 06:16:18,079 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1135303073] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-08 06:16:18,079 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-08 06:16:18,079 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-04-08 06:16:18,080 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:16:18,080 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1514678305] [2022-04-08 06:16:18,080 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1514678305] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:16:18,080 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:16:18,080 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-08 06:16:18,080 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [599429778] [2022-04-08 06:16:18,080 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:16:18,081 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 43 [2022-04-08 06:16:18,081 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:16:18,081 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-08 06:16:18,121 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 34 edges. 34 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:16:18,121 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-08 06:16:18,121 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:16:18,121 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-08 06:16:18,122 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2022-04-08 06:16:18,122 INFO L87 Difference]: Start difference. First operand 40 states and 43 transitions. Second operand has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-08 06:16:19,095 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:16:19,096 INFO L93 Difference]: Finished difference Result 50 states and 54 transitions. [2022-04-08 06:16:19,096 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-08 06:16:19,096 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 43 [2022-04-08 06:16:19,096 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:16:19,096 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-08 06:16:19,098 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 48 transitions. [2022-04-08 06:16:19,098 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-08 06:16:19,099 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 48 transitions. [2022-04-08 06:16:19,099 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 9 states and 48 transitions. [2022-04-08 06:16:19,203 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 48 edges. 48 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:16:19,204 INFO L225 Difference]: With dead ends: 50 [2022-04-08 06:16:19,204 INFO L226 Difference]: Without dead ends: 47 [2022-04-08 06:16:19,205 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 74 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=45, Invalid=137, Unknown=0, NotChecked=0, Total=182 [2022-04-08 06:16:19,205 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 12 mSDsluCounter, 147 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 175 SdHoareTripleChecker+Invalid, 113 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2022-04-08 06:16:19,205 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 175 Invalid, 113 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2022-04-08 06:16:19,206 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2022-04-08 06:16:19,232 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2022-04-08 06:16:19,232 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:16:19,234 INFO L82 GeneralOperation]: Start isEquivalent. First operand 47 states. Second operand has 47 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 10 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-08 06:16:19,234 INFO L74 IsIncluded]: Start isIncluded. First operand 47 states. Second operand has 47 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 10 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-08 06:16:19,234 INFO L87 Difference]: Start difference. First operand 47 states. Second operand has 47 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 10 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-08 06:16:19,239 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:16:19,239 INFO L93 Difference]: Finished difference Result 47 states and 50 transitions. [2022-04-08 06:16:19,239 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 50 transitions. [2022-04-08 06:16:19,240 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:16:19,240 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:16:19,240 INFO L74 IsIncluded]: Start isIncluded. First operand has 47 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 10 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 47 states. [2022-04-08 06:16:19,241 INFO L87 Difference]: Start difference. First operand has 47 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 10 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand 47 states. [2022-04-08 06:16:19,245 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:16:19,245 INFO L93 Difference]: Finished difference Result 47 states and 50 transitions. [2022-04-08 06:16:19,245 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 50 transitions. [2022-04-08 06:16:19,246 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:16:19,246 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:16:19,246 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:16:19,246 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:16:19,246 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 30 states have (on average 1.0666666666666667) internal successors, (32), 31 states have internal predecessors, (32), 10 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-08 06:16:19,249 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 50 transitions. [2022-04-08 06:16:19,249 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 50 transitions. Word has length 43 [2022-04-08 06:16:19,250 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:16:19,250 INFO L478 AbstractCegarLoop]: Abstraction has 47 states and 50 transitions. [2022-04-08 06:16:19,250 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-08 06:16:19,250 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 47 states and 50 transitions. [2022-04-08 06:16:19,336 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 50 edges. 50 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:16:19,337 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 50 transitions. [2022-04-08 06:16:19,337 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-04-08 06:16:19,337 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 06:16:19,338 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 06:16:19,360 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-08 06:16:19,538 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:16:19,538 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 06:16:19,539 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 06:16:19,539 INFO L85 PathProgramCache]: Analyzing trace with hash 1099019754, now seen corresponding path program 5 times [2022-04-08 06:16:19,539 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 06:16:19,539 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [146222045] [2022-04-08 06:16:19,539 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 06:16:19,539 INFO L85 PathProgramCache]: Analyzing trace with hash 1099019754, now seen corresponding path program 6 times [2022-04-08 06:16:19,539 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 06:16:19,539 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [625147269] [2022-04-08 06:16:19,539 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 06:16:19,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 06:16:19,573 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 06:16:19,573 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [323791110] [2022-04-08 06:16:19,573 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-08 06:16:19,573 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:16:19,573 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 06:16:19,578 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-08 06:16:19,579 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-08 06:16:20,871 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2022-04-08 06:16:20,871 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 06:16:20,874 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 24 conjunts are in the unsatisfiable core [2022-04-08 06:16:20,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 06:16:20,915 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 06:16:32,824 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-08 06:16:38,043 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-08 06:16:44,992 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-08 06:17:26,757 WARN L232 SmtUtils]: Spent 24.84s on a formula simplification. DAG size of input: 46 DAG size of output: 38 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-08 06:17:40,021 INFO L272 TraceCheckUtils]: 0: Hoare triple {1606#true} call ULTIMATE.init(); {1606#true} is VALID [2022-04-08 06:17:40,022 INFO L290 TraceCheckUtils]: 1: Hoare triple {1606#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3); {1606#true} is VALID [2022-04-08 06:17:40,022 INFO L290 TraceCheckUtils]: 2: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-08 06:17:40,022 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1606#true} {1606#true} #65#return; {1606#true} is VALID [2022-04-08 06:17:40,022 INFO L272 TraceCheckUtils]: 4: Hoare triple {1606#true} call #t~ret7 := main(); {1606#true} is VALID [2022-04-08 06:17:40,022 INFO L290 TraceCheckUtils]: 5: Hoare triple {1606#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {1606#true} is VALID [2022-04-08 06:17:40,022 INFO L272 TraceCheckUtils]: 6: Hoare triple {1606#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 100 then 1 else 0)); {1606#true} is VALID [2022-04-08 06:17:40,022 INFO L290 TraceCheckUtils]: 7: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-08 06:17:40,022 INFO L290 TraceCheckUtils]: 8: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-08 06:17:40,022 INFO L290 TraceCheckUtils]: 9: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-08 06:17:40,022 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1606#true} {1606#true} #55#return; {1606#true} is VALID [2022-04-08 06:17:40,023 INFO L290 TraceCheckUtils]: 11: Hoare triple {1606#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {1606#true} is VALID [2022-04-08 06:17:40,023 INFO L272 TraceCheckUtils]: 12: Hoare triple {1606#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 100 then 1 else 0)); {1606#true} is VALID [2022-04-08 06:17:40,023 INFO L290 TraceCheckUtils]: 13: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-08 06:17:40,023 INFO L290 TraceCheckUtils]: 14: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-08 06:17:40,023 INFO L290 TraceCheckUtils]: 15: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-08 06:17:40,023 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1606#true} {1606#true} #57#return; {1606#true} is VALID [2022-04-08 06:17:40,023 INFO L290 TraceCheckUtils]: 17: Hoare triple {1606#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {1606#true} is VALID [2022-04-08 06:17:40,023 INFO L272 TraceCheckUtils]: 18: Hoare triple {1606#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 100 then 1 else 0)); {1606#true} is VALID [2022-04-08 06:17:40,023 INFO L290 TraceCheckUtils]: 19: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-08 06:17:40,023 INFO L290 TraceCheckUtils]: 20: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-08 06:17:40,024 INFO L290 TraceCheckUtils]: 21: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-08 06:17:40,024 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1606#true} {1606#true} #59#return; {1606#true} is VALID [2022-04-08 06:17:40,029 INFO L290 TraceCheckUtils]: 23: Hoare triple {1606#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:17:40,032 INFO L290 TraceCheckUtils]: 24: Hoare triple {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:17:40,033 INFO L272 TraceCheckUtils]: 25: Hoare triple {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1606#true} is VALID [2022-04-08 06:17:40,033 INFO L290 TraceCheckUtils]: 26: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-08 06:17:40,033 INFO L290 TraceCheckUtils]: 27: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-08 06:17:40,033 INFO L290 TraceCheckUtils]: 28: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-08 06:17:40,034 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {1606#true} {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} #61#return; {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:17:40,034 INFO L290 TraceCheckUtils]: 30: Hoare triple {1680#(and (= main_~y~0 1) (= main_~a~0 main_~x~0) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} is VALID [2022-04-08 06:17:40,035 INFO L290 TraceCheckUtils]: 31: Hoare triple {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} assume !false; {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} is VALID [2022-04-08 06:17:40,035 INFO L272 TraceCheckUtils]: 32: Hoare triple {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1606#true} is VALID [2022-04-08 06:17:40,035 INFO L290 TraceCheckUtils]: 33: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-08 06:17:40,035 INFO L290 TraceCheckUtils]: 34: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-08 06:17:40,035 INFO L290 TraceCheckUtils]: 35: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-08 06:17:40,036 INFO L284 TraceCheckUtils]: 36: Hoare quadruple {1606#true} {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} #61#return; {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} is VALID [2022-04-08 06:17:40,036 INFO L290 TraceCheckUtils]: 37: Hoare triple {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} is VALID [2022-04-08 06:17:40,036 INFO L290 TraceCheckUtils]: 38: Hoare triple {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} assume !false; {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} is VALID [2022-04-08 06:17:40,036 INFO L272 TraceCheckUtils]: 39: Hoare triple {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1606#true} is VALID [2022-04-08 06:17:40,037 INFO L290 TraceCheckUtils]: 40: Hoare triple {1606#true} ~cond := #in~cond; {1733#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:17:40,038 INFO L290 TraceCheckUtils]: 41: Hoare triple {1733#(= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)} assume !(0 == ~cond); {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:17:40,039 INFO L290 TraceCheckUtils]: 42: Hoare triple {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:17:40,040 INFO L284 TraceCheckUtils]: 43: Hoare quadruple {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} {1702#(= (* main_~a~0 main_~z~0) main_~az~0)} #61#return; {1744#(and (= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:17:42,042 WARN L290 TraceCheckUtils]: 44: Hoare triple {1744#(and (= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0)) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1748#(and (or (and (= 0 (mod (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) (or (and (= (mod main_~y~0 main_~z~0) 0) (= (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) (+ main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0))) (= main_~az~0 0)) (and (= (mod (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) 0) (not (= main_~az~0 0)) (= (* (div (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) main_~z~0) main_~y~0))) (not (= main_~z~0 0))) (and (= main_~z~0 0) (= main_~y~0 0) (= main_~a~0 main_~x~0))) (= (* main_~a~0 main_~z~0) main_~az~0))} is UNKNOWN [2022-04-08 06:17:42,044 INFO L290 TraceCheckUtils]: 45: Hoare triple {1748#(and (or (and (= 0 (mod (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) (or (and (= (mod main_~y~0 main_~z~0) 0) (= (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) (+ main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0))) (= main_~az~0 0)) (and (= (mod (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) 0) (not (= main_~az~0 0)) (= (* (div (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) main_~z~0) main_~y~0))) (not (= main_~z~0 0))) (and (= main_~z~0 0) (= main_~y~0 0) (= main_~a~0 main_~x~0))) (= (* main_~a~0 main_~z~0) main_~az~0))} assume !false; {1748#(and (or (and (= 0 (mod (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) (or (and (= (mod main_~y~0 main_~z~0) 0) (= (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) (+ main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0))) (= main_~az~0 0)) (and (= (mod (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) 0) (not (= main_~az~0 0)) (= (* (div (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) main_~z~0) main_~y~0))) (not (= main_~z~0 0))) (and (= main_~z~0 0) (= main_~y~0 0) (= main_~a~0 main_~x~0))) (= (* main_~a~0 main_~z~0) main_~az~0))} is VALID [2022-04-08 06:17:42,121 INFO L272 TraceCheckUtils]: 46: Hoare triple {1748#(and (or (and (= 0 (mod (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) (or (and (= (mod main_~y~0 main_~z~0) 0) (= (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) (+ main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0))) (= main_~az~0 0)) (and (= (mod (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) 0) (not (= main_~az~0 0)) (= (* (div (+ (* (- 1) (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0)) main_~a~0 (* (div (+ (* (- 1) main_~a~0) main_~x~0) main_~z~0) main_~z~0)) main_~az~0) main_~z~0) main_~y~0))) (not (= main_~z~0 0))) (and (= main_~z~0 0) (= main_~y~0 0) (= main_~a~0 main_~x~0))) (= (* main_~a~0 main_~z~0) main_~az~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1755#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 06:17:42,123 INFO L290 TraceCheckUtils]: 47: Hoare triple {1755#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1759#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:17:42,124 INFO L290 TraceCheckUtils]: 48: Hoare triple {1759#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1607#false} is VALID [2022-04-08 06:17:42,124 INFO L290 TraceCheckUtils]: 49: Hoare triple {1607#false} assume !false; {1607#false} is VALID [2022-04-08 06:17:42,124 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 16 proven. 9 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2022-04-08 06:17:42,124 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-08 06:18:12,401 INFO L290 TraceCheckUtils]: 49: Hoare triple {1607#false} assume !false; {1607#false} is VALID [2022-04-08 06:18:12,402 INFO L290 TraceCheckUtils]: 48: Hoare triple {1759#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1607#false} is VALID [2022-04-08 06:18:12,402 INFO L290 TraceCheckUtils]: 47: Hoare triple {1755#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1759#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 06:18:12,403 INFO L272 TraceCheckUtils]: 46: Hoare triple {1775#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1755#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 06:18:12,415 INFO L290 TraceCheckUtils]: 45: Hoare triple {1775#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} assume !false; {1775#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} is VALID [2022-04-08 06:18:12,440 INFO L290 TraceCheckUtils]: 44: Hoare triple {1782#(= (+ (* main_~z~0 main_~x~0) main_~a~0 (* main_~az~0 (* main_~z~0 main_~y~0))) (+ main_~a~0 (* main_~z~0 (+ (* main_~z~0 main_~x~0) main_~a~0))))} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1775#(= (+ (* main_~y~0 main_~az~0) main_~x~0) (+ (* main_~z~0 main_~x~0) main_~a~0))} is VALID [2022-04-08 06:18:12,445 INFO L284 TraceCheckUtils]: 43: Hoare quadruple {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} {1606#true} #61#return; {1782#(= (+ (* main_~z~0 main_~x~0) main_~a~0 (* main_~az~0 (* main_~z~0 main_~y~0))) (+ main_~a~0 (* main_~z~0 (+ (* main_~z~0 main_~x~0) main_~a~0))))} is VALID [2022-04-08 06:18:12,446 INFO L290 TraceCheckUtils]: 42: Hoare triple {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} assume true; {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:18:12,446 INFO L290 TraceCheckUtils]: 41: Hoare triple {1795#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} assume !(0 == ~cond); {1737#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-08 06:18:12,446 INFO L290 TraceCheckUtils]: 40: Hoare triple {1606#true} ~cond := #in~cond; {1795#(or (not (= |__VERIFIER_assert_#in~cond| 0)) (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-08 06:18:12,447 INFO L272 TraceCheckUtils]: 39: Hoare triple {1606#true} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1606#true} is VALID [2022-04-08 06:18:12,447 INFO L290 TraceCheckUtils]: 38: Hoare triple {1606#true} assume !false; {1606#true} is VALID [2022-04-08 06:18:12,447 INFO L290 TraceCheckUtils]: 37: Hoare triple {1606#true} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1606#true} is VALID [2022-04-08 06:18:12,447 INFO L284 TraceCheckUtils]: 36: Hoare quadruple {1606#true} {1606#true} #61#return; {1606#true} is VALID [2022-04-08 06:18:12,447 INFO L290 TraceCheckUtils]: 35: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-08 06:18:12,447 INFO L290 TraceCheckUtils]: 34: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-08 06:18:12,447 INFO L290 TraceCheckUtils]: 33: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-08 06:18:12,447 INFO L272 TraceCheckUtils]: 32: Hoare triple {1606#true} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1606#true} is VALID [2022-04-08 06:18:12,448 INFO L290 TraceCheckUtils]: 31: Hoare triple {1606#true} assume !false; {1606#true} is VALID [2022-04-08 06:18:12,448 INFO L290 TraceCheckUtils]: 30: Hoare triple {1606#true} assume !!(~c~0 < ~k~0);~c~0 := 1 + ~c~0;~x~0 := ~x~0 * ~z~0 + ~a~0;~y~0 := ~y~0 * ~z~0; {1606#true} is VALID [2022-04-08 06:18:12,448 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {1606#true} {1606#true} #61#return; {1606#true} is VALID [2022-04-08 06:18:12,448 INFO L290 TraceCheckUtils]: 28: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-08 06:18:12,448 INFO L290 TraceCheckUtils]: 27: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-08 06:18:12,448 INFO L290 TraceCheckUtils]: 26: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-08 06:18:12,448 INFO L272 TraceCheckUtils]: 25: Hoare triple {1606#true} call __VERIFIER_assert((if 0 == ~z~0 * ~x~0 - ~x~0 + ~a~0 - ~az~0 * ~y~0 then 1 else 0)); {1606#true} is VALID [2022-04-08 06:18:12,448 INFO L290 TraceCheckUtils]: 24: Hoare triple {1606#true} assume !false; {1606#true} is VALID [2022-04-08 06:18:12,449 INFO L290 TraceCheckUtils]: 23: Hoare triple {1606#true} ~x~0 := ~a~0;~y~0 := 1;~c~0 := 1;~az~0 := ~a~0 * ~z~0; {1606#true} is VALID [2022-04-08 06:18:12,449 INFO L284 TraceCheckUtils]: 22: Hoare quadruple {1606#true} {1606#true} #59#return; {1606#true} is VALID [2022-04-08 06:18:12,449 INFO L290 TraceCheckUtils]: 21: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-08 06:18:12,449 INFO L290 TraceCheckUtils]: 20: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-08 06:18:12,449 INFO L290 TraceCheckUtils]: 19: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-08 06:18:12,449 INFO L272 TraceCheckUtils]: 18: Hoare triple {1606#true} call assume_abort_if_not((if ~k~0 >= 0 && ~k~0 <= 100 then 1 else 0)); {1606#true} is VALID [2022-04-08 06:18:12,449 INFO L290 TraceCheckUtils]: 17: Hoare triple {1606#true} assume -2147483648 <= #t~nondet6 && #t~nondet6 <= 2147483647;~k~0 := #t~nondet6;havoc #t~nondet6; {1606#true} is VALID [2022-04-08 06:18:12,449 INFO L284 TraceCheckUtils]: 16: Hoare quadruple {1606#true} {1606#true} #57#return; {1606#true} is VALID [2022-04-08 06:18:12,450 INFO L290 TraceCheckUtils]: 15: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-08 06:18:12,450 INFO L290 TraceCheckUtils]: 14: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-08 06:18:12,450 INFO L290 TraceCheckUtils]: 13: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-08 06:18:12,450 INFO L272 TraceCheckUtils]: 12: Hoare triple {1606#true} call assume_abort_if_not((if ~a~0 >= 0 && ~a~0 <= 100 then 1 else 0)); {1606#true} is VALID [2022-04-08 06:18:12,450 INFO L290 TraceCheckUtils]: 11: Hoare triple {1606#true} assume -2147483648 <= #t~nondet5 && #t~nondet5 <= 2147483647;~a~0 := #t~nondet5;havoc #t~nondet5; {1606#true} is VALID [2022-04-08 06:18:12,450 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1606#true} {1606#true} #55#return; {1606#true} is VALID [2022-04-08 06:18:12,450 INFO L290 TraceCheckUtils]: 9: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-08 06:18:12,450 INFO L290 TraceCheckUtils]: 8: Hoare triple {1606#true} assume !(0 == ~cond); {1606#true} is VALID [2022-04-08 06:18:12,451 INFO L290 TraceCheckUtils]: 7: Hoare triple {1606#true} ~cond := #in~cond; {1606#true} is VALID [2022-04-08 06:18:12,451 INFO L272 TraceCheckUtils]: 6: Hoare triple {1606#true} call assume_abort_if_not((if ~z~0 >= 0 && ~z~0 <= 100 then 1 else 0)); {1606#true} is VALID [2022-04-08 06:18:12,451 INFO L290 TraceCheckUtils]: 5: Hoare triple {1606#true} havoc ~z~0;havoc ~a~0;havoc ~k~0;havoc ~x~0;havoc ~y~0;havoc ~c~0;havoc ~az~0;assume -2147483648 <= #t~nondet4 && #t~nondet4 <= 2147483647;~z~0 := #t~nondet4;havoc #t~nondet4; {1606#true} is VALID [2022-04-08 06:18:12,451 INFO L272 TraceCheckUtils]: 4: Hoare triple {1606#true} call #t~ret7 := main(); {1606#true} is VALID [2022-04-08 06:18:12,451 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1606#true} {1606#true} #65#return; {1606#true} is VALID [2022-04-08 06:18:12,451 INFO L290 TraceCheckUtils]: 2: Hoare triple {1606#true} assume true; {1606#true} is VALID [2022-04-08 06:18:12,451 INFO L290 TraceCheckUtils]: 1: Hoare triple {1606#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(10, 2);call #Ultimate.allocInit(12, 3); {1606#true} is VALID [2022-04-08 06:18:12,451 INFO L272 TraceCheckUtils]: 0: Hoare triple {1606#true} call ULTIMATE.init(); {1606#true} is VALID [2022-04-08 06:18:12,452 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 19 proven. 1 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2022-04-08 06:18:12,452 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 06:18:12,452 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [625147269] [2022-04-08 06:18:12,452 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 06:18:12,452 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [323791110] [2022-04-08 06:18:12,452 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [323791110] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-08 06:18:12,453 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-08 06:18:12,453 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 13 [2022-04-08 06:18:12,453 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 06:18:12,453 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [146222045] [2022-04-08 06:18:12,453 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [146222045] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 06:18:12,453 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 06:18:12,453 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-04-08 06:18:12,453 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [921239451] [2022-04-08 06:18:12,453 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 06:18:12,454 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) Word has length 50 [2022-04-08 06:18:12,454 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 06:18:12,454 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-08 06:18:14,543 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 39 edges. 38 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-08 06:18:14,544 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-08 06:18:14,544 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 06:18:14,544 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-08 06:18:14,544 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2022-04-08 06:18:14,544 INFO L87 Difference]: Start difference. First operand 47 states and 50 transitions. Second operand has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-08 06:18:23,044 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:18:23,045 INFO L93 Difference]: Finished difference Result 47 states and 50 transitions. [2022-04-08 06:18:23,045 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-08 06:18:23,045 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) Word has length 50 [2022-04-08 06:18:23,045 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 06:18:23,045 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-08 06:18:23,046 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 33 transitions. [2022-04-08 06:18:23,046 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-08 06:18:23,047 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 33 transitions. [2022-04-08 06:18:23,047 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 6 states and 33 transitions. [2022-04-08 06:18:27,159 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 33 edges. 31 inductive. 0 not inductive. 2 times theorem prover too weak to decide inductivity. [2022-04-08 06:18:27,159 INFO L225 Difference]: With dead ends: 47 [2022-04-08 06:18:27,159 INFO L226 Difference]: Without dead ends: 0 [2022-04-08 06:18:27,160 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 87 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 36 ImplicationChecksByTransitivity, 25.4s TimeCoverageRelationStatistics Valid=46, Invalid=136, Unknown=0, NotChecked=0, Total=182 [2022-04-08 06:18:27,160 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 11 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-04-08 06:18:27,160 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 126 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-04-08 06:18:27,161 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-08 06:18:27,161 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-08 06:18:27,161 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 06:18:27,161 INFO L82 GeneralOperation]: Start isEquivalent. First operand 0 states. Second operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-08 06:18:27,161 INFO L74 IsIncluded]: Start isIncluded. First operand 0 states. Second operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-08 06:18:27,161 INFO L87 Difference]: Start difference. First operand 0 states. Second operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-08 06:18:27,161 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:18:27,161 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-08 06:18:27,161 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-08 06:18:27,162 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:18:27,162 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:18:27,162 INFO L74 IsIncluded]: Start isIncluded. First operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand 0 states. [2022-04-08 06:18:27,162 INFO L87 Difference]: Start difference. First operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand 0 states. [2022-04-08 06:18:27,162 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 06:18:27,162 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-04-08 06:18:27,162 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-08 06:18:27,162 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:18:27,162 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 06:18:27,162 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 06:18:27,162 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 06:18:27,162 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-08 06:18:27,162 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-08 06:18:27,162 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 50 [2022-04-08 06:18:27,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 06:18:27,162 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-08 06:18:27,163 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 4 states have call predecessors, (7), 3 states have call successors, (7) [2022-04-08 06:18:27,163 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 0 states and 0 transitions. [2022-04-08 06:18:27,163 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 0 edges. 0 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 06:18:27,163 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-08 06:18:27,163 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 06:18:27,165 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-08 06:18:27,191 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-08 06:18:27,384 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 06:18:27,386 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-04-08 06:19:00,223 WARN L232 SmtUtils]: Spent 32.80s on a formula simplification. DAG size of input: 53 DAG size of output: 43 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-08 06:19:23,550 WARN L232 SmtUtils]: Spent 23.32s on a formula simplification. DAG size of input: 53 DAG size of output: 43 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-08 06:20:15,935 WARN L232 SmtUtils]: Spent 52.37s on a formula simplification. DAG size of input: 53 DAG size of output: 50 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-08 06:20:49,515 WARN L232 SmtUtils]: Spent 33.55s on a formula simplification. DAG size of input: 53 DAG size of output: 43 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-08 06:20:49,554 INFO L882 garLoopResultBuilder]: For program point reach_errorEXIT(line 8) no Hoare annotation was computed. [2022-04-08 06:20:49,554 INFO L882 garLoopResultBuilder]: For program point reach_errorENTRY(line 8) no Hoare annotation was computed. [2022-04-08 06:20:49,554 INFO L882 garLoopResultBuilder]: For program point reach_errorFINAL(line 8) no Hoare annotation was computed. [2022-04-08 06:20:49,554 INFO L885 garLoopResultBuilder]: At program point assume_abort_if_notENTRY(lines 11 13) the Hoare annotation is: true [2022-04-08 06:20:49,554 INFO L878 garLoopResultBuilder]: At program point L12(line 12) the Hoare annotation is: (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|) [2022-04-08 06:20:49,554 INFO L878 garLoopResultBuilder]: At program point L12-2(lines 11 13) the Hoare annotation is: (and (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)) [2022-04-08 06:20:49,555 INFO L878 garLoopResultBuilder]: At program point assume_abort_if_notEXIT(lines 11 13) the Hoare annotation is: (and (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)) [2022-04-08 06:20:49,555 INFO L885 garLoopResultBuilder]: At program point L29(line 29) the Hoare annotation is: true [2022-04-08 06:20:49,555 INFO L885 garLoopResultBuilder]: At program point L29-1(line 29) the Hoare annotation is: true [2022-04-08 06:20:49,555 INFO L885 garLoopResultBuilder]: At program point L27(line 27) the Hoare annotation is: true [2022-04-08 06:20:49,555 INFO L885 garLoopResultBuilder]: At program point L27-1(line 27) the Hoare annotation is: true [2022-04-08 06:20:49,555 INFO L885 garLoopResultBuilder]: At program point L25(line 25) the Hoare annotation is: true [2022-04-08 06:20:49,555 INFO L885 garLoopResultBuilder]: At program point mainEXIT(lines 21 48) the Hoare annotation is: true [2022-04-08 06:20:49,555 INFO L885 garLoopResultBuilder]: At program point L25-1(line 25) the Hoare annotation is: true [2022-04-08 06:20:49,555 INFO L885 garLoopResultBuilder]: At program point L46(line 46) the Hoare annotation is: true [2022-04-08 06:20:49,555 INFO L885 garLoopResultBuilder]: At program point mainFINAL(lines 21 48) the Hoare annotation is: true [2022-04-08 06:20:49,555 INFO L878 garLoopResultBuilder]: At program point L36-2(lines 36 45) the Hoare annotation is: (let ((.cse0 (= main_~a~0 main_~x~0)) (.cse1 (= (* main_~a~0 main_~z~0) main_~az~0))) (or (and (= main_~y~0 1) .cse0 .cse1) (and (let ((.cse7 (= main_~z~0 0))) (or (let ((.cse2 (+ (* (- 1) main_~a~0) main_~x~0))) (and (= 0 (mod .cse2 main_~z~0)) (let ((.cse3 (div .cse2 main_~z~0))) (let ((.cse5 (= main_~az~0 0)) (.cse4 (* .cse3 main_~z~0))) (or (and (= (mod main_~y~0 main_~z~0) 0) (= .cse3 (+ main_~a~0 .cse4)) .cse5) (let ((.cse6 (+ (* (- 1) .cse3) main_~a~0 .cse4))) (and (= (mod .cse6 main_~az~0) 0) (not .cse5) (= (* (div .cse6 main_~az~0) main_~z~0) main_~y~0)))))) (not .cse7))) (and .cse7 (= main_~y~0 0) .cse0))) .cse1))) [2022-04-08 06:20:49,555 INFO L878 garLoopResultBuilder]: At program point L36-3(lines 36 45) the Hoare annotation is: (let ((.cse1 (* main_~a~0 main_~z~0))) (let ((.cse0 (= .cse1 main_~az~0))) (or (and (= main_~y~0 1) (= main_~a~0 main_~x~0) .cse0) (and (= main_~x~0 (+ .cse1 main_~a~0 (* main_~a~0 main_~z~0 main_~z~0))) (= (* main_~z~0 main_~z~0) main_~y~0) .cse0) (let ((.cse2 (+ (* (- 1) main_~a~0) main_~x~0))) (and (= 0 (mod .cse2 main_~z~0)) (let ((.cse3 (div .cse2 main_~z~0))) (let ((.cse5 (= main_~az~0 0)) (.cse4 (* .cse3 main_~z~0))) (or (and (= (mod main_~y~0 main_~z~0) 0) (= .cse3 (+ main_~a~0 .cse4)) .cse5) (let ((.cse6 (+ (* (- 1) .cse3) main_~a~0 .cse4))) (and (= (mod .cse6 main_~az~0) 0) (not .cse5) (= (* (div .cse6 main_~az~0) main_~z~0) main_~y~0)))))) (not (= main_~z~0 0)) .cse0)) (and (= main_~z~0 main_~y~0) (= main_~x~0 (+ .cse1 main_~a~0)) .cse0)))) [2022-04-08 06:20:49,555 INFO L885 garLoopResultBuilder]: At program point mainENTRY(lines 21 48) the Hoare annotation is: true [2022-04-08 06:20:49,555 INFO L878 garLoopResultBuilder]: At program point L37(line 37) the Hoare annotation is: (let ((.cse0 (= main_~a~0 main_~x~0)) (.cse1 (= (* main_~a~0 main_~z~0) main_~az~0))) (or (and (= main_~y~0 1) .cse0 .cse1) (and (let ((.cse7 (= main_~z~0 0))) (or (let ((.cse2 (+ (* (- 1) main_~a~0) main_~x~0))) (and (= 0 (mod .cse2 main_~z~0)) (let ((.cse3 (div .cse2 main_~z~0))) (let ((.cse5 (= main_~az~0 0)) (.cse4 (* .cse3 main_~z~0))) (or (and (= (mod main_~y~0 main_~z~0) 0) (= .cse3 (+ main_~a~0 .cse4)) .cse5) (let ((.cse6 (+ (* (- 1) .cse3) main_~a~0 .cse4))) (and (= (mod .cse6 main_~az~0) 0) (not .cse5) (= (* (div .cse6 main_~az~0) main_~z~0) main_~y~0)))))) (not .cse7))) (and .cse7 (= main_~y~0 0) .cse0))) .cse1))) [2022-04-08 06:20:49,556 INFO L878 garLoopResultBuilder]: At program point L37-1(lines 36 45) the Hoare annotation is: (let ((.cse0 (= main_~a~0 main_~x~0)) (.cse1 (= (* main_~a~0 main_~z~0) main_~az~0))) (or (and (= main_~y~0 1) .cse0 .cse1) (and (let ((.cse7 (= main_~z~0 0))) (or (let ((.cse2 (+ (* (- 1) main_~a~0) main_~x~0))) (and (= 0 (mod .cse2 main_~z~0)) (let ((.cse3 (div .cse2 main_~z~0))) (let ((.cse5 (= main_~az~0 0)) (.cse4 (* .cse3 main_~z~0))) (or (and (= (mod main_~y~0 main_~z~0) 0) (= .cse3 (+ main_~a~0 .cse4)) .cse5) (let ((.cse6 (+ (* (- 1) .cse3) main_~a~0 .cse4))) (and (= (mod .cse6 main_~az~0) 0) (not .cse5) (= (* (div .cse6 main_~az~0) main_~z~0) main_~y~0)))))) (not .cse7))) (and .cse7 (= main_~y~0 0) .cse0))) .cse1))) [2022-04-08 06:20:49,556 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.initFINAL(line -1) the Hoare annotation is: true [2022-04-08 06:20:49,556 INFO L878 garLoopResultBuilder]: At program point ULTIMATE.initENTRY(line -1) the Hoare annotation is: (and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|)) [2022-04-08 06:20:49,556 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.initEXIT(line -1) the Hoare annotation is: true [2022-04-08 06:20:49,556 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startEXIT(line -1) the Hoare annotation is: true [2022-04-08 06:20:49,556 INFO L885 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-04-08 06:20:49,556 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-04-08 06:20:49,556 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startFINAL(line -1) the Hoare annotation is: true [2022-04-08 06:20:49,556 INFO L878 garLoopResultBuilder]: At program point L16(lines 16 17) the Hoare annotation is: (not (<= 1 |__VERIFIER_assert_#in~cond|)) [2022-04-08 06:20:49,556 INFO L878 garLoopResultBuilder]: At program point L15(lines 15 18) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-08 06:20:49,556 INFO L885 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 14 20) the Hoare annotation is: true [2022-04-08 06:20:49,556 INFO L878 garLoopResultBuilder]: At program point L15-2(lines 14 20) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-08 06:20:49,556 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertEXIT(lines 14 20) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-08 06:20:49,556 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 17) the Hoare annotation is: (not (<= 1 |__VERIFIER_assert_#in~cond|)) [2022-04-08 06:20:49,558 INFO L719 BasicCegarLoop]: Path program histogram: [6, 2, 2] [2022-04-08 06:20:49,559 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-04-08 06:20:49,561 WARN L170 areAnnotationChecker]: reach_errorENTRY has no Hoare annotation [2022-04-08 06:20:49,568 WARN L170 areAnnotationChecker]: reach_errorFINAL has no Hoare annotation [2022-04-08 06:20:51,580 INFO L163 areAnnotationChecker]: CFG has 38 edges. 37 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. 0 times interpolants missing. [2022-04-08 06:20:51,591 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 08.04 06:20:51 BoogieIcfgContainer [2022-04-08 06:20:51,591 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-08 06:20:51,592 INFO L158 Benchmark]: Toolchain (without parser) took 299609.34ms. Allocated memory was 197.1MB in the beginning and 251.7MB in the end (delta: 54.5MB). Free memory was 148.9MB in the beginning and 121.1MB in the end (delta: 27.8MB). Peak memory consumption was 82.6MB. Max. memory is 8.0GB. [2022-04-08 06:20:51,592 INFO L158 Benchmark]: CDTParser took 0.11ms. Allocated memory is still 197.1MB. Free memory is still 165.6MB. There was no memory consumed. Max. memory is 8.0GB. [2022-04-08 06:20:51,592 INFO L158 Benchmark]: CACSL2BoogieTranslator took 234.46ms. Allocated memory is still 197.1MB. Free memory was 148.8MB in the beginning and 172.7MB in the end (delta: -23.9MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-08 06:20:51,592 INFO L158 Benchmark]: Boogie Preprocessor took 32.66ms. Allocated memory is still 197.1MB. Free memory was 172.7MB in the beginning and 171.3MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-04-08 06:20:51,593 INFO L158 Benchmark]: RCFGBuilder took 279.78ms. Allocated memory is still 197.1MB. Free memory was 171.3MB in the beginning and 159.7MB in the end (delta: 11.6MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-08 06:20:51,593 INFO L158 Benchmark]: TraceAbstraction took 299057.66ms. Allocated memory was 197.1MB in the beginning and 251.7MB in the end (delta: 54.5MB). Free memory was 159.3MB in the beginning and 121.1MB in the end (delta: 38.2MB). Peak memory consumption was 93.5MB. Max. memory is 8.0GB. [2022-04-08 06:20:51,594 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - AssertionsEnabledResult: Assertions are enabled Assertions are enabled - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.11ms. Allocated memory is still 197.1MB. Free memory is still 165.6MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 234.46ms. Allocated memory is still 197.1MB. Free memory was 148.8MB in the beginning and 172.7MB in the end (delta: -23.9MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Preprocessor took 32.66ms. Allocated memory is still 197.1MB. Free memory was 172.7MB in the beginning and 171.3MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 279.78ms. Allocated memory is still 197.1MB. Free memory was 171.3MB in the beginning and 159.7MB in the end (delta: 11.6MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * TraceAbstraction took 299057.66ms. Allocated memory was 197.1MB in the beginning and 251.7MB in the end (delta: 54.5MB). Free memory was 159.3MB in the beginning and 121.1MB in the end (delta: 38.2MB). Peak memory consumption was 93.5MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 17]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 34 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 297.0s, OverallIterations: 5, TraceHistogramMax: 4, PathProgramHistogramMax: 6, EmptinessCheckTime: 0.0s, AutomataDifference: 15.6s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 142.2s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 69 SdHoareTripleChecker+Valid, 1.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 60 mSDsluCounter, 575 SdHoareTripleChecker+Invalid, 1.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 445 mSDsCounter, 21 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 320 IncrementalHoareTripleChecker+Invalid, 341 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 21 mSolverCounterUnsat, 130 mSDtfsCounter, 320 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 303 GetRequests, 257 SyntacticMatches, 3 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 25.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=47occurred in iteration=4, InterpolantAutomatonStates: 33, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 5 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 31 LocationsWithAnnotation, 101 PreInvPairs, 161 NumberOfFragments, 614 HoareAnnotationTreeSize, 101 FomulaSimplifications, 0 FormulaSimplificationTreeSizeReduction, 0.0s HoareSimplificationTime, 31 FomulaSimplificationsInter, 884 FormulaSimplificationTreeSizeReductionInter, 142.1s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: No data available, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 36]: Loop Invariant Derived loop invariant: ((y == 1 && a == x) && a * z == az) || ((((0 == (-1 * a + x) % z && (((y % z == 0 && (-1 * a + x) / z == a + (-1 * a + x) / z * z) && az == 0) || (((-1 * ((-1 * a + x) / z) + a + (-1 * a + x) / z * z) % az == 0 && !(az == 0)) && (-1 * ((-1 * a + x) / z) + a + (-1 * a + x) / z * z) / az * z == y))) && !(z == 0)) || ((z == 0 && y == 0) && a == x)) && a * z == az) - ProcedureContractResult [Line: 11]: Procedure Contract for assume_abort_if_not Derived contract for procedure assume_abort_if_not: !(\old(cond) == 0) && cond == \old(cond) - ProcedureContractResult [Line: 21]: Procedure Contract for main Derived contract for procedure main: 1 - ProcedureContractResult [Line: 14]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert: \old(cond) == cond || !(1 <= \old(cond)) RESULT: Ultimate proved your program to be correct! [2022-04-08 06:20:51,638 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...