/usr/bin/java -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/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-5d317bd [2022-03-18 19:33:19,244 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-18 19:33:19,245 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-18 19:33:19,277 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-18 19:33:19,277 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-18 19:33:19,278 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-18 19:33:19,282 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-18 19:33:19,300 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-18 19:33:19,302 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-18 19:33:19,303 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-18 19:33:19,303 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-18 19:33:19,304 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-18 19:33:19,305 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-18 19:33:19,305 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-18 19:33:19,306 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-18 19:33:19,307 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-18 19:33:19,308 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-18 19:33:19,308 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-18 19:33:19,309 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-18 19:33:19,312 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-18 19:33:19,313 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-18 19:33:19,314 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-18 19:33:19,314 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-18 19:33:19,315 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-18 19:33:19,316 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-18 19:33:19,318 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-18 19:33:19,318 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-18 19:33:19,318 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-18 19:33:19,319 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-18 19:33:19,319 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-18 19:33:19,320 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-18 19:33:19,320 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-18 19:33:19,321 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-18 19:33:19,321 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-18 19:33:19,322 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-18 19:33:19,323 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-18 19:33:19,323 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-18 19:33:19,323 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-18 19:33:19,324 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-18 19:33:19,324 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-18 19:33:19,324 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-18 19:33:19,325 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-18 19:33:19,326 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-03-18 19:33:19,333 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-18 19:33:19,334 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-18 19:33:19,335 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-18 19:33:19,335 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-18 19:33:19,335 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-18 19:33:19,335 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-18 19:33:19,335 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-18 19:33:19,335 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-18 19:33:19,335 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-18 19:33:19,335 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-18 19:33:19,336 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-18 19:33:19,336 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-18 19:33:19,336 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-18 19:33:19,336 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-18 19:33:19,336 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-18 19:33:19,336 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-18 19:33:19,336 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-18 19:33:19,337 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-18 19:33:19,337 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-18 19:33:19,337 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-18 19:33:19,337 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-18 19:33:19,337 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-18 19:33:19,338 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_JORDAN 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-03-18 19:33:19,568 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-18 19:33:19,589 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-18 19:33:19,591 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-18 19:33:19,592 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-18 19:33:19,593 INFO L275 PluginConnector]: CDTParser initialized [2022-03-18 19:33:19,594 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound100.c [2022-03-18 19:33:19,647 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/89ae708f7/094a572a81704f93b372f89ca5a5c03f/FLAG5d9a3ee46 [2022-03-18 19:33:20,023 INFO L306 CDTParser]: Found 1 translation units. [2022-03-18 19:33:20,024 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound100.c [2022-03-18 19:33:20,029 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/89ae708f7/094a572a81704f93b372f89ca5a5c03f/FLAG5d9a3ee46 [2022-03-18 19:33:20,434 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/89ae708f7/094a572a81704f93b372f89ca5a5c03f [2022-03-18 19:33:20,436 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-18 19:33:20,438 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-18 19:33:20,440 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-18 19:33:20,440 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-18 19:33:20,446 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-18 19:33:20,447 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.03 07:33:20" (1/1) ... [2022-03-18 19:33:20,447 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@d89072f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 07:33:20, skipping insertion in model container [2022-03-18 19:33:20,448 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.03 07:33:20" (1/1) ... [2022-03-18 19:33:20,453 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-18 19:33:20,466 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-18 19:33:20,602 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/hard-ll_valuebound100.c[538,551] [2022-03-18 19:33:20,618 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-18 19:33:20,624 INFO L203 MainTranslator]: Completed pre-run [2022-03-18 19:33:20,634 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/hard-ll_valuebound100.c[538,551] [2022-03-18 19:33:20,640 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-18 19:33:20,649 INFO L208 MainTranslator]: Completed translation [2022-03-18 19:33:20,650 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 07:33:20 WrapperNode [2022-03-18 19:33:20,650 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-18 19:33:20,651 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-18 19:33:20,651 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-18 19:33:20,651 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-18 19:33:20,660 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 07:33:20" (1/1) ... [2022-03-18 19:33:20,660 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 07:33:20" (1/1) ... [2022-03-18 19:33:20,667 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 07:33:20" (1/1) ... [2022-03-18 19:33:20,667 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 07:33:20" (1/1) ... [2022-03-18 19:33:20,680 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 07:33:20" (1/1) ... [2022-03-18 19:33:20,685 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 07:33:20" (1/1) ... [2022-03-18 19:33:20,691 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 07:33:20" (1/1) ... [2022-03-18 19:33:20,693 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-18 19:33:20,693 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-18 19:33:20,693 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-18 19:33:20,693 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-18 19:33:20,695 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 07:33:20" (1/1) ... [2022-03-18 19:33:20,700 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-18 19:33:20,708 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 19:33:20,721 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-03-18 19:33:20,744 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-03-18 19:33:20,765 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-18 19:33:20,765 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-18 19:33:20,766 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-18 19:33:20,766 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-18 19:33:20,766 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-18 19:33:20,767 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-18 19:33:20,767 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-18 19:33:20,767 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-18 19:33:20,767 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-18 19:33:20,767 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-18 19:33:20,767 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-03-18 19:33:20,767 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-18 19:33:20,768 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-18 19:33:20,768 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-18 19:33:20,768 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-18 19:33:20,769 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-18 19:33:20,769 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-18 19:33:20,769 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-18 19:33:20,769 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-18 19:33:20,769 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-18 19:33:20,829 INFO L234 CfgBuilder]: Building ICFG [2022-03-18 19:33:20,830 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-18 19:33:20,989 INFO L275 CfgBuilder]: Performing block encoding [2022-03-18 19:33:20,994 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-18 19:33:20,994 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-18 19:33:20,996 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.03 07:33:20 BoogieIcfgContainer [2022-03-18 19:33:20,996 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-18 19:33:21,011 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-18 19:33:21,012 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-18 19:33:21,013 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-18 19:33:21,019 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.03 07:33:20" (1/1) ... [2022-03-18 19:33:21,034 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 18.03 07:33:21 BasicIcfg [2022-03-18 19:33:21,034 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-18 19:33:21,035 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-18 19:33:21,035 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-18 19:33:21,037 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-18 19:33:21,038 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.03 07:33:20" (1/4) ... [2022-03-18 19:33:21,038 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3e73a543 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.03 07:33:21, skipping insertion in model container [2022-03-18 19:33:21,038 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.03 07:33:20" (2/4) ... [2022-03-18 19:33:21,039 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3e73a543 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.03 07:33:21, skipping insertion in model container [2022-03-18 19:33:21,039 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.03 07:33:20" (3/4) ... [2022-03-18 19:33:21,039 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3e73a543 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.03 07:33:21, skipping insertion in model container [2022-03-18 19:33:21,039 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 18.03 07:33:21" (4/4) ... [2022-03-18 19:33:21,040 INFO L111 eAbstractionObserver]: Analyzing ICFG hard-ll_valuebound100.cJordan [2022-03-18 19:33:21,044 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-03-18 19:33:21,044 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-18 19:33:21,084 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-18 19:33:21,089 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=ForwardPredicates, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, 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-03-18 19:33:21,089 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-18 19:33:21,103 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-18 19:33:21,109 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-18 19:33:21,109 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:33:21,110 INFO L500 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] [2022-03-18 19:33:21,110 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:33:21,114 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:33:21,114 INFO L85 PathProgramCache]: Analyzing trace with hash 1011787902, now seen corresponding path program 1 times [2022-03-18 19:33:21,122 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:33:21,123 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1589096550] [2022-03-18 19:33:21,123 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:33:21,123 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:33:21,221 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:21,291 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-18 19:33:21,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:21,309 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-18 19:33:21,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:21,331 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-18 19:33:21,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:21,350 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-18 19:33:21,352 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:21,358 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-18 19:33:21,359 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:33:21,359 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1589096550] [2022-03-18 19:33:21,360 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1589096550] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 19:33:21,360 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 19:33:21,360 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-18 19:33:21,361 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [613979479] [2022-03-18 19:33:21,362 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 19:33:21,365 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-18 19:33:21,365 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:33:21,396 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-18 19:33:21,397 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-18 19:33:21,399 INFO L87 Difference]: Start difference. First operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (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-03-18 19:33:21,479 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:33:21,480 INFO L93 Difference]: Finished difference Result 38 states and 48 transitions. [2022-03-18 19:33:21,481 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-18 19:33:21,482 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (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 28 [2022-03-18 19:33:21,482 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:33:21,492 INFO L225 Difference]: With dead ends: 38 [2022-03-18 19:33:21,493 INFO L226 Difference]: Without dead ends: 33 [2022-03-18 19:33:21,494 INFO L911 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-03-18 19:33:21,497 INFO L912 BasicCegarLoop]: 38 mSDtfsCounter, 21 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 19:33:21,498 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 41 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 19:33:21,512 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-03-18 19:33:21,531 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-03-18 19:33:21,532 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-18 19:33:21,534 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2022-03-18 19:33:21,535 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 28 [2022-03-18 19:33:21,536 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:33:21,536 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2022-03-18 19:33:21,536 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (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-03-18 19:33:21,537 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-03-18 19:33:21,539 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-18 19:33:21,539 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:33:21,539 INFO L500 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] [2022-03-18 19:33:21,540 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-18 19:33:21,540 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:33:21,541 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:33:21,541 INFO L85 PathProgramCache]: Analyzing trace with hash -1710049411, now seen corresponding path program 1 times [2022-03-18 19:33:21,541 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:33:21,542 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1081776608] [2022-03-18 19:33:21,542 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:33:21,543 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:33:21,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:21,679 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-18 19:33:21,681 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:21,685 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-18 19:33:21,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:21,692 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-18 19:33:21,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:21,702 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-18 19:33:21,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:21,709 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-18 19:33:21,709 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:33:21,709 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1081776608] [2022-03-18 19:33:21,709 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1081776608] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 19:33:21,710 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 19:33:21,710 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-18 19:33:21,710 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [524471107] [2022-03-18 19:33:21,710 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 19:33:21,714 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-18 19:33:21,714 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:33:21,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-18 19:33:21,716 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-18 19:33:21,716 INFO L87 Difference]: Start difference. First operand 33 states and 43 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-03-18 19:33:21,903 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:33:21,904 INFO L93 Difference]: Finished difference Result 44 states and 58 transitions. [2022-03-18 19:33:21,904 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-18 19:33:21,904 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 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 28 [2022-03-18 19:33:21,904 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:33:21,905 INFO L225 Difference]: With dead ends: 44 [2022-03-18 19:33:21,905 INFO L226 Difference]: Without dead ends: 44 [2022-03-18 19:33:21,906 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-18 19:33:21,907 INFO L912 BasicCegarLoop]: 31 mSDtfsCounter, 38 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 155 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 19:33:21,907 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 48 Invalid, 155 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 19:33:21,908 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-03-18 19:33:21,914 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-03-18 19:33:21,914 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-18 19:33:21,915 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 46 transitions. [2022-03-18 19:33:21,915 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 46 transitions. Word has length 28 [2022-03-18 19:33:21,916 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:33:21,916 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 46 transitions. [2022-03-18 19:33:21,916 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-03-18 19:33:21,916 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 46 transitions. [2022-03-18 19:33:21,917 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-03-18 19:33:21,917 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:33:21,917 INFO L500 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 19:33:21,917 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-18 19:33:21,917 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:33:21,918 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:33:21,918 INFO L85 PathProgramCache]: Analyzing trace with hash 1042498848, now seen corresponding path program 1 times [2022-03-18 19:33:21,918 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:33:21,918 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [487812673] [2022-03-18 19:33:21,918 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:33:21,919 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:33:21,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:21,994 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-18 19:33:21,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:22,000 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-18 19:33:22,001 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:22,004 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-18 19:33:22,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:22,008 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-18 19:33:22,008 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:22,012 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2022-03-18 19:33:22,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:22,018 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-18 19:33:22,018 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:33:22,018 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [487812673] [2022-03-18 19:33:22,018 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [487812673] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 19:33:22,018 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 19:33:22,018 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-18 19:33:22,019 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [319099777] [2022-03-18 19:33:22,019 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 19:33:22,019 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-18 19:33:22,019 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:33:22,020 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-18 19:33:22,020 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-18 19:33:22,020 INFO L87 Difference]: Start difference. First operand 37 states and 46 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-18 19:33:22,229 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:33:22,229 INFO L93 Difference]: Finished difference Result 48 states and 61 transitions. [2022-03-18 19:33:22,230 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-18 19:33:22,230 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-03-18 19:33:22,230 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:33:22,231 INFO L225 Difference]: With dead ends: 48 [2022-03-18 19:33:22,231 INFO L226 Difference]: Without dead ends: 48 [2022-03-18 19:33:22,231 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-18 19:33:22,232 INFO L912 BasicCegarLoop]: 31 mSDtfsCounter, 33 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-18 19:33:22,233 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 48 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 132 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-18 19:33:22,233 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-03-18 19:33:22,238 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 41. [2022-03-18 19:33:22,238 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-18 19:33:22,251 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2022-03-18 19:33:22,252 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 33 [2022-03-18 19:33:22,252 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:33:22,252 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2022-03-18 19:33:22,252 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-18 19:33:22,252 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2022-03-18 19:33:22,253 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-03-18 19:33:22,253 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:33:22,253 INFO L500 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 19:33:22,253 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-03-18 19:33:22,254 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:33:22,254 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:33:22,254 INFO L85 PathProgramCache]: Analyzing trace with hash 1436069466, now seen corresponding path program 1 times [2022-03-18 19:33:22,254 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:33:22,255 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [354338898] [2022-03-18 19:33:22,255 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:33:22,255 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:33:22,289 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 19:33:22,290 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [604388501] [2022-03-18 19:33:22,290 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:33:22,290 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:33:22,290 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 19:33:22,303 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-03-18 19:33:22,313 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-03-18 19:33:22,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:22,361 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-18 19:33:22,366 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 19:33:22,596 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2022-03-18 19:33:22,596 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-18 19:33:22,596 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:33:22,596 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [354338898] [2022-03-18 19:33:22,597 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 19:33:22,597 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [604388501] [2022-03-18 19:33:22,597 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [604388501] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 19:33:22,597 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 19:33:22,597 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-03-18 19:33:22,598 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1824641744] [2022-03-18 19:33:22,598 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 19:33:22,598 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-18 19:33:22,599 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:33:22,599 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-18 19:33:22,599 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2022-03-18 19:33:22,600 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-18 19:33:22,739 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:33:22,739 INFO L93 Difference]: Finished difference Result 56 states and 70 transitions. [2022-03-18 19:33:22,740 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-18 19:33:22,740 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) Word has length 38 [2022-03-18 19:33:22,741 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:33:22,746 INFO L225 Difference]: With dead ends: 56 [2022-03-18 19:33:22,746 INFO L226 Difference]: Without dead ends: 55 [2022-03-18 19:33:22,747 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2022-03-18 19:33:22,755 INFO L912 BasicCegarLoop]: 40 mSDtfsCounter, 20 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 225 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 19:33:22,755 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 225 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 99 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 19:33:22,756 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-03-18 19:33:22,768 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-03-18 19:33:22,770 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 30 states have (on average 1.1666666666666667) internal successors, (35), 32 states have internal predecessors, (35), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-03-18 19:33:22,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-03-18 19:33:22,776 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 38 [2022-03-18 19:33:22,777 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:33:22,777 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-03-18 19:33:22,777 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-18 19:33:22,777 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-03-18 19:33:22,778 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-03-18 19:33:22,778 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:33:22,778 INFO L500 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 19:33:22,804 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-18 19:33:22,979 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:33:22,979 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:33:22,980 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:33:22,980 INFO L85 PathProgramCache]: Analyzing trace with hash 5711864, now seen corresponding path program 1 times [2022-03-18 19:33:22,980 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:33:22,980 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [810247663] [2022-03-18 19:33:22,981 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:33:22,981 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:33:22,993 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 19:33:22,993 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2077306555] [2022-03-18 19:33:22,993 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:33:22,993 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:33:22,993 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 19:33:23,000 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-03-18 19:33:23,012 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-03-18 19:33:23,047 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:23,048 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-18 19:33:23,057 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 19:33:23,383 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 9 proven. 3 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-03-18 19:33:23,383 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 19:33:23,556 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-18 19:33:23,556 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:33:23,556 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [810247663] [2022-03-18 19:33:23,556 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 19:33:23,556 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2077306555] [2022-03-18 19:33:23,556 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2077306555] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-18 19:33:23,557 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-18 19:33:23,557 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [9] total 11 [2022-03-18 19:33:23,557 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2064523250] [2022-03-18 19:33:23,557 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 19:33:23,557 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-18 19:33:23,558 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:33:23,558 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-18 19:33:23,558 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-03-18 19:33:23,558 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-18 19:33:23,616 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:33:23,616 INFO L93 Difference]: Finished difference Result 66 states and 83 transitions. [2022-03-18 19:33:23,617 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 19:33:23,617 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 45 [2022-03-18 19:33:23,617 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:33:23,618 INFO L225 Difference]: With dead ends: 66 [2022-03-18 19:33:23,618 INFO L226 Difference]: Without dead ends: 66 [2022-03-18 19:33:23,619 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-03-18 19:33:23,619 INFO L912 BasicCegarLoop]: 42 mSDtfsCounter, 12 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 178 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 19:33:23,620 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [18 Valid, 178 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 19:33:23,620 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-03-18 19:33:23,625 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 64. [2022-03-18 19:33:23,625 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 36 states have (on average 1.1944444444444444) internal successors, (43), 38 states have internal predecessors, (43), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-03-18 19:33:23,626 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 80 transitions. [2022-03-18 19:33:23,626 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 80 transitions. Word has length 45 [2022-03-18 19:33:23,627 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:33:23,627 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 80 transitions. [2022-03-18 19:33:23,627 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-18 19:33:23,627 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 80 transitions. [2022-03-18 19:33:23,628 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-03-18 19:33:23,628 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:33:23,629 INFO L500 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 19:33:23,648 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-03-18 19:33:23,839 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:33:23,840 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:33:23,840 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:33:23,840 INFO L85 PathProgramCache]: Analyzing trace with hash 1597443315, now seen corresponding path program 1 times [2022-03-18 19:33:23,840 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:33:23,840 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [469241459] [2022-03-18 19:33:23,841 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:33:23,841 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:33:23,851 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 19:33:23,851 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1375811779] [2022-03-18 19:33:23,852 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:33:23,852 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:33:23,852 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 19:33:23,853 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-03-18 19:33:23,858 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-03-18 19:33:23,898 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:23,899 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 16 conjunts are in the unsatisfiable core [2022-03-18 19:33:23,902 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 19:33:24,114 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 16 proven. 4 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2022-03-18 19:33:24,114 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 19:33:24,252 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2022-03-18 19:33:24,252 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:33:24,252 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [469241459] [2022-03-18 19:33:24,252 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 19:33:24,252 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1375811779] [2022-03-18 19:33:24,252 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1375811779] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-18 19:33:24,252 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-18 19:33:24,253 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-03-18 19:33:24,253 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1406250667] [2022-03-18 19:33:24,253 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 19:33:24,253 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 19:33:24,253 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:33:24,254 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 19:33:24,254 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-03-18 19:33:24,254 INFO L87 Difference]: Start difference. First operand 64 states and 80 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-18 19:33:24,309 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:33:24,309 INFO L93 Difference]: Finished difference Result 74 states and 93 transitions. [2022-03-18 19:33:24,309 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 19:33:24,309 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 55 [2022-03-18 19:33:24,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:33:24,310 INFO L225 Difference]: With dead ends: 74 [2022-03-18 19:33:24,310 INFO L226 Difference]: Without dead ends: 74 [2022-03-18 19:33:24,311 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 99 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-03-18 19:33:24,311 INFO L912 BasicCegarLoop]: 41 mSDtfsCounter, 8 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 19:33:24,312 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 141 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 19:33:24,312 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2022-03-18 19:33:24,317 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2022-03-18 19:33:24,318 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 40 states have (on average 1.175) internal successors, (47), 43 states have internal predecessors, (47), 22 states have call successors, (22), 9 states have call predecessors, (22), 8 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-03-18 19:33:24,318 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 88 transitions. [2022-03-18 19:33:24,318 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 88 transitions. Word has length 55 [2022-03-18 19:33:24,319 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:33:24,319 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 88 transitions. [2022-03-18 19:33:24,319 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-18 19:33:24,319 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 88 transitions. [2022-03-18 19:33:24,320 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-03-18 19:33:24,320 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:33:24,320 INFO L500 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 19:33:24,347 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-03-18 19:33:24,520 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:33:24,521 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:33:24,521 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:33:24,521 INFO L85 PathProgramCache]: Analyzing trace with hash 810354846, now seen corresponding path program 1 times [2022-03-18 19:33:24,522 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:33:24,522 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1703792758] [2022-03-18 19:33:24,522 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:33:24,522 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:33:24,532 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 19:33:24,532 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [47144271] [2022-03-18 19:33:24,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:33:24,532 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:33:24,532 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 19:33:24,539 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-03-18 19:33:24,545 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-03-18 19:33:24,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:24,596 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-18 19:33:24,598 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 19:33:24,722 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-03-18 19:33:24,722 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-18 19:33:24,722 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:33:24,722 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1703792758] [2022-03-18 19:33:24,722 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 19:33:24,723 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [47144271] [2022-03-18 19:33:24,723 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [47144271] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 19:33:24,723 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 19:33:24,723 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-18 19:33:24,723 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [389580635] [2022-03-18 19:33:24,723 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 19:33:24,725 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 19:33:24,725 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:33:24,726 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 19:33:24,726 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-18 19:33:24,726 INFO L87 Difference]: Start difference. First operand 71 states and 88 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-03-18 19:33:24,774 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:33:24,774 INFO L93 Difference]: Finished difference Result 77 states and 94 transitions. [2022-03-18 19:33:24,775 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 19:33:24,775 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 56 [2022-03-18 19:33:24,777 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:33:24,787 INFO L225 Difference]: With dead ends: 77 [2022-03-18 19:33:24,787 INFO L226 Difference]: Without dead ends: 72 [2022-03-18 19:33:24,788 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 52 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-03-18 19:33:24,788 INFO L912 BasicCegarLoop]: 36 mSDtfsCounter, 8 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 19:33:24,789 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 132 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 19:33:24,789 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2022-03-18 19:33:24,794 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 71. [2022-03-18 19:33:24,794 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 41 states have (on average 1.146341463414634) internal successors, (47), 44 states have internal predecessors, (47), 20 states have call successors, (20), 10 states have call predecessors, (20), 9 states have return successors, (18), 16 states have call predecessors, (18), 18 states have call successors, (18) [2022-03-18 19:33:24,795 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 85 transitions. [2022-03-18 19:33:24,795 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 85 transitions. Word has length 56 [2022-03-18 19:33:24,795 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:33:24,795 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 85 transitions. [2022-03-18 19:33:24,795 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-03-18 19:33:24,795 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 85 transitions. [2022-03-18 19:33:24,796 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-03-18 19:33:24,796 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:33:24,797 INFO L500 BasicCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 19:33:24,819 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-03-18 19:33:25,011 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:33:25,012 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:33:25,012 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:33:25,012 INFO L85 PathProgramCache]: Analyzing trace with hash 1689231171, now seen corresponding path program 1 times [2022-03-18 19:33:25,012 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:33:25,012 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [317287501] [2022-03-18 19:33:25,012 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:33:25,013 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:33:25,022 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 19:33:25,022 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1982802473] [2022-03-18 19:33:25,022 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:33:25,023 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:33:25,023 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 19:33:25,024 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 19:33:25,040 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-18 19:33:25,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:33:25,103 INFO L263 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 30 conjunts are in the unsatisfiable core [2022-03-18 19:33:25,106 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 19:33:25,819 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 36 proven. 8 refuted. 0 times theorem prover too weak. 103 trivial. 0 not checked. [2022-03-18 19:33:25,819 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 19:33:56,109 WARN L232 SmtUtils]: Spent 16.49s on a formula simplification that was a NOOP. DAG size: 53 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 19:34:58,853 WARN L232 SmtUtils]: Spent 17.49s on a formula simplification that was a NOOP. DAG size: 54 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 19:35:53,693 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 36 proven. 8 refuted. 0 times theorem prover too weak. 103 trivial. 0 not checked. [2022-03-18 19:35:53,694 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:35:53,694 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [317287501] [2022-03-18 19:35:53,694 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 19:35:53,694 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1982802473] [2022-03-18 19:35:53,694 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1982802473] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 19:35:53,694 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 19:35:53,694 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12] total 18 [2022-03-18 19:35:53,695 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1642987322] [2022-03-18 19:35:53,695 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 19:35:53,695 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2022-03-18 19:35:53,695 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:35:53,696 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-03-18 19:35:53,696 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=241, Unknown=0, NotChecked=0, Total=306 [2022-03-18 19:35:53,696 INFO L87 Difference]: Start difference. First operand 71 states and 85 transitions. Second operand has 18 states, 18 states have (on average 2.0) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) [2022-03-18 19:35:55,711 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 19:35:58,121 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 19:36:04,068 WARN L232 SmtUtils]: Spent 5.78s on a formula simplification. DAG size of input: 57 DAG size of output: 27 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 19:36:07,062 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse4 (<= c_main_~d~0 c_main_~r~0)) (.cse0 (mod c_main_~A~0 4294967296)) (.cse2 (mod c_main_~B~0 4294967296))) (and (let ((.cse1 (* 2 c_main_~p~0)) (.cse3 (* 2 c_main_~d~0))) (or (= .cse0 (+ (* (+ c_main_~q~0 (div .cse1 2)) .cse2) (* (- 1) (div .cse3 2)) c_main_~r~0)) (not (= (* .cse1 .cse2) .cse3)) (not .cse4) (<= .cse3 c_main_~r~0))) (or .cse4 (not (= c_main_~d~0 (* c_main_~p~0 .cse2))) (let ((.cse7 (= (mod c_main_~p~0 2) 0)) (.cse13 (div c_main_~p~0 2))) (let ((.cse9 (* (+ c_main_~q~0 .cse13) .cse2)) (.cse10 (not .cse7)) (.cse5 (* (- 1) (div c_main_~d~0 2))) (.cse6 (* (+ c_main_~q~0 .cse13 1) .cse2)) (.cse12 (= (mod c_main_~d~0 2) 0)) (.cse11 (< c_main_~d~0 0))) (and (or (let ((.cse8 (< c_main_~p~0 0))) (and (or (= .cse0 (+ c_main_~r~0 .cse5 .cse6)) .cse7 (not .cse8)) (or (= .cse0 (+ .cse9 c_main_~r~0 .cse5)) (and .cse10 .cse8)))) (and .cse11 (not .cse12))) (or (and (or (= .cse0 (+ (- 1) .cse9 c_main_~r~0 .cse5)) .cse10) (or .cse7 (= .cse0 (+ (- 1) c_main_~r~0 .cse5 .cse6)))) .cse12 (not .cse11)))))))) is different from true [2022-03-18 19:36:08,740 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:36:08,740 INFO L93 Difference]: Finished difference Result 117 states and 150 transitions. [2022-03-18 19:36:08,740 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-03-18 19:36:08,741 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 2.0) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) Word has length 75 [2022-03-18 19:36:08,741 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:36:08,742 INFO L225 Difference]: With dead ends: 117 [2022-03-18 19:36:08,742 INFO L226 Difference]: Without dead ends: 117 [2022-03-18 19:36:08,742 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 131 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 85 ImplicationChecksByTransitivity, 44.2s TimeCoverageRelationStatistics Valid=107, Invalid=402, Unknown=1, NotChecked=42, Total=552 [2022-03-18 19:36:08,743 INFO L912 BasicCegarLoop]: 38 mSDtfsCounter, 62 mSDsluCounter, 246 mSDsCounter, 0 mSdLazyCounter, 342 mSolverCounterSat, 131 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 67 SdHoareTripleChecker+Valid, 284 SdHoareTripleChecker+Invalid, 481 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 131 IncrementalHoareTripleChecker+Valid, 342 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 6 IncrementalHoareTripleChecker+Unchecked, 6.6s IncrementalHoareTripleChecker+Time [2022-03-18 19:36:08,743 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [67 Valid, 284 Invalid, 481 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [131 Valid, 342 Invalid, 2 Unknown, 6 Unchecked, 6.6s Time] [2022-03-18 19:36:08,744 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2022-03-18 19:36:08,750 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 103. [2022-03-18 19:36:08,756 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 60 states have (on average 1.15) internal successors, (69), 65 states have internal predecessors, (69), 30 states have call successors, (30), 13 states have call predecessors, (30), 12 states have return successors, (28), 24 states have call predecessors, (28), 28 states have call successors, (28) [2022-03-18 19:36:08,757 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 127 transitions. [2022-03-18 19:36:08,757 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 127 transitions. Word has length 75 [2022-03-18 19:36:08,757 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:36:08,757 INFO L478 AbstractCegarLoop]: Abstraction has 103 states and 127 transitions. [2022-03-18 19:36:08,758 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 2.0) internal successors, (36), 16 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (20), 8 states have call predecessors, (20), 7 states have call successors, (20) [2022-03-18 19:36:08,758 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 127 transitions. [2022-03-18 19:36:08,759 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2022-03-18 19:36:08,759 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:36:08,759 INFO L500 BasicCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 19:36:08,779 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-03-18 19:36:08,971 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:36:08,971 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:36:08,972 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:36:08,972 INFO L85 PathProgramCache]: Analyzing trace with hash -102783885, now seen corresponding path program 1 times [2022-03-18 19:36:08,972 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:36:08,972 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [152950687] [2022-03-18 19:36:08,973 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:36:08,973 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:36:08,983 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 19:36:08,983 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [735923225] [2022-03-18 19:36:08,983 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:36:08,983 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:36:08,983 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 19:36:08,988 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 19:36:08,989 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-18 19:36:09,039 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:36:09,040 INFO L263 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-18 19:36:09,042 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 19:36:09,293 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 20 proven. 4 refuted. 0 times theorem prover too weak. 197 trivial. 0 not checked. [2022-03-18 19:36:09,294 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 19:36:09,536 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 20 proven. 4 refuted. 0 times theorem prover too weak. 197 trivial. 0 not checked. [2022-03-18 19:36:09,536 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:36:09,536 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [152950687] [2022-03-18 19:36:09,537 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 19:36:09,537 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [735923225] [2022-03-18 19:36:09,537 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [735923225] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 19:36:09,537 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 19:36:09,537 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2022-03-18 19:36:09,537 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [312403135] [2022-03-18 19:36:09,537 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 19:36:09,538 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-18 19:36:09,538 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:36:09,538 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-18 19:36:09,538 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2022-03-18 19:36:09,539 INFO L87 Difference]: Start difference. First operand 103 states and 127 transitions. Second operand has 9 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2022-03-18 19:36:09,660 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:36:09,660 INFO L93 Difference]: Finished difference Result 114 states and 141 transitions. [2022-03-18 19:36:09,661 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-18 19:36:09,661 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) Word has length 86 [2022-03-18 19:36:09,661 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:36:09,662 INFO L225 Difference]: With dead ends: 114 [2022-03-18 19:36:09,662 INFO L226 Difference]: Without dead ends: 114 [2022-03-18 19:36:09,663 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 162 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2022-03-18 19:36:09,663 INFO L912 BasicCegarLoop]: 44 mSDtfsCounter, 13 mSDsluCounter, 214 mSDsCounter, 0 mSdLazyCounter, 100 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 258 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 100 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-18 19:36:09,663 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 258 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 100 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-18 19:36:09,664 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2022-03-18 19:36:09,669 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 107. [2022-03-18 19:36:09,670 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 62 states have (on average 1.1612903225806452) internal successors, (72), 67 states have internal predecessors, (72), 32 states have call successors, (32), 13 states have call predecessors, (32), 12 states have return successors, (30), 26 states have call predecessors, (30), 30 states have call successors, (30) [2022-03-18 19:36:09,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 134 transitions. [2022-03-18 19:36:09,671 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 134 transitions. Word has length 86 [2022-03-18 19:36:09,671 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:36:09,671 INFO L478 AbstractCegarLoop]: Abstraction has 107 states and 134 transitions. [2022-03-18 19:36:09,671 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 3.5714285714285716) internal successors, (25), 8 states have internal predecessors, (25), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2022-03-18 19:36:09,671 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 134 transitions. [2022-03-18 19:36:09,672 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2022-03-18 19:36:09,672 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:36:09,673 INFO L500 BasicCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 19:36:09,702 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-18 19:36:09,895 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:36:09,896 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:36:09,896 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:36:09,896 INFO L85 PathProgramCache]: Analyzing trace with hash 1406960063, now seen corresponding path program 2 times [2022-03-18 19:36:09,896 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:36:09,896 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1442109176] [2022-03-18 19:36:09,896 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:36:09,896 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:36:09,904 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 19:36:09,905 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [760858723] [2022-03-18 19:36:09,905 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-18 19:36:09,905 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:36:09,905 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 19:36:09,912 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 19:36:09,914 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-18 19:36:09,957 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-18 19:36:09,957 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 19:36:09,958 INFO L263 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-18 19:36:09,960 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 19:36:10,089 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2022-03-18 19:36:10,089 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 19:36:10,250 INFO L134 CoverageAnalysis]: Checked inductivity of 226 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2022-03-18 19:36:10,251 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:36:10,251 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1442109176] [2022-03-18 19:36:10,251 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 19:36:10,251 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [760858723] [2022-03-18 19:36:10,251 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [760858723] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 19:36:10,251 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 19:36:10,252 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2022-03-18 19:36:10,252 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [661787761] [2022-03-18 19:36:10,252 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 19:36:10,252 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 19:36:10,253 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:36:10,253 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 19:36:10,253 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-18 19:36:10,253 INFO L87 Difference]: Start difference. First operand 107 states and 134 transitions. Second operand has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 5 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 4 states have call predecessors, (19), 4 states have call successors, (19) [2022-03-18 19:36:10,290 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:36:10,290 INFO L93 Difference]: Finished difference Result 111 states and 140 transitions. [2022-03-18 19:36:10,290 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-03-18 19:36:10,291 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 5 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 4 states have call predecessors, (19), 4 states have call successors, (19) Word has length 88 [2022-03-18 19:36:10,291 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:36:10,292 INFO L225 Difference]: With dead ends: 111 [2022-03-18 19:36:10,292 INFO L226 Difference]: Without dead ends: 111 [2022-03-18 19:36:10,293 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 171 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-18 19:36:10,293 INFO L912 BasicCegarLoop]: 56 mSDtfsCounter, 1 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 19:36:10,295 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 139 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 19:36:10,295 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2022-03-18 19:36:10,302 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 111. [2022-03-18 19:36:10,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 64 states have (on average 1.15625) internal successors, (74), 69 states have internal predecessors, (74), 34 states have call successors, (34), 13 states have call predecessors, (34), 12 states have return successors, (32), 28 states have call predecessors, (32), 32 states have call successors, (32) [2022-03-18 19:36:10,303 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 140 transitions. [2022-03-18 19:36:10,303 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 140 transitions. Word has length 88 [2022-03-18 19:36:10,303 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:36:10,303 INFO L478 AbstractCegarLoop]: Abstraction has 111 states and 140 transitions. [2022-03-18 19:36:10,303 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.0) internal successors, (30), 5 states have internal predecessors, (30), 5 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (19), 4 states have call predecessors, (19), 4 states have call successors, (19) [2022-03-18 19:36:10,304 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 140 transitions. [2022-03-18 19:36:10,305 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-03-18 19:36:10,305 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:36:10,305 INFO L500 BasicCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 19:36:10,330 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-03-18 19:36:10,527 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:36:10,527 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:36:10,528 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:36:10,528 INFO L85 PathProgramCache]: Analyzing trace with hash 966352941, now seen corresponding path program 1 times [2022-03-18 19:36:10,528 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:36:10,528 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [323696748] [2022-03-18 19:36:10,528 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:36:10,528 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:36:10,536 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 19:36:10,537 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1121630374] [2022-03-18 19:36:10,537 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:36:10,537 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:36:10,537 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 19:36:10,538 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 19:36:10,576 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-18 19:36:10,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:36:10,597 INFO L263 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-18 19:36:10,599 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 19:36:10,838 INFO L134 CoverageAnalysis]: Checked inductivity of 263 backedges. 22 proven. 9 refuted. 0 times theorem prover too weak. 232 trivial. 0 not checked. [2022-03-18 19:36:10,839 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 19:36:11,252 INFO L134 CoverageAnalysis]: Checked inductivity of 263 backedges. 22 proven. 9 refuted. 0 times theorem prover too weak. 232 trivial. 0 not checked. [2022-03-18 19:36:11,252 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:36:11,253 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [323696748] [2022-03-18 19:36:11,253 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 19:36:11,253 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1121630374] [2022-03-18 19:36:11,253 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1121630374] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 19:36:11,253 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 19:36:11,253 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2022-03-18 19:36:11,253 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1259627196] [2022-03-18 19:36:11,253 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 19:36:11,254 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-18 19:36:11,254 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:36:11,254 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-18 19:36:11,254 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-03-18 19:36:11,255 INFO L87 Difference]: Start difference. First operand 111 states and 140 transitions. Second operand has 11 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 8 states have call successors, (29), 2 states have call predecessors, (29), 1 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2022-03-18 19:36:11,555 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:36:11,556 INFO L93 Difference]: Finished difference Result 117 states and 146 transitions. [2022-03-18 19:36:11,556 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-18 19:36:11,556 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 8 states have call successors, (29), 2 states have call predecessors, (29), 1 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 91 [2022-03-18 19:36:11,556 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:36:11,557 INFO L225 Difference]: With dead ends: 117 [2022-03-18 19:36:11,557 INFO L226 Difference]: Without dead ends: 102 [2022-03-18 19:36:11,558 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 171 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=139, Unknown=0, NotChecked=0, Total=182 [2022-03-18 19:36:11,558 INFO L912 BasicCegarLoop]: 58 mSDtfsCounter, 10 mSDsluCounter, 350 mSDsCounter, 0 mSdLazyCounter, 135 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 408 SdHoareTripleChecker+Invalid, 147 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 135 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-18 19:36:11,558 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 408 Invalid, 147 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 135 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-18 19:36:11,559 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2022-03-18 19:36:11,563 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 102. [2022-03-18 19:36:11,564 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 59 states have (on average 1.152542372881356) internal successors, (68), 64 states have internal predecessors, (68), 30 states have call successors, (30), 13 states have call predecessors, (30), 12 states have return successors, (28), 24 states have call predecessors, (28), 28 states have call successors, (28) [2022-03-18 19:36:11,564 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 126 transitions. [2022-03-18 19:36:11,565 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 126 transitions. Word has length 91 [2022-03-18 19:36:11,565 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:36:11,565 INFO L478 AbstractCegarLoop]: Abstraction has 102 states and 126 transitions. [2022-03-18 19:36:11,565 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.0) internal successors, (33), 10 states have internal predecessors, (33), 8 states have call successors, (29), 2 states have call predecessors, (29), 1 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2022-03-18 19:36:11,565 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 126 transitions. [2022-03-18 19:36:11,566 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2022-03-18 19:36:11,566 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:36:11,566 INFO L500 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 19:36:11,591 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-18 19:36:11,786 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-03-18 19:36:11,786 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:36:11,787 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:36:11,787 INFO L85 PathProgramCache]: Analyzing trace with hash -1871497790, now seen corresponding path program 1 times [2022-03-18 19:36:11,787 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:36:11,787 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1985086889] [2022-03-18 19:36:11,787 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:36:11,787 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:36:11,795 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 19:36:11,795 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [552330247] [2022-03-18 19:36:11,795 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:36:11,795 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:36:11,796 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 19:36:11,797 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 19:36:11,808 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-03-18 19:36:11,840 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-18 19:36:11,841 INFO L263 TraceCheckSpWp]: Trace formula consists of 212 conjuncts, 4 conjunts are in the unsatisfiable core [2022-03-18 19:36:11,843 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 19:36:12,015 INFO L134 CoverageAnalysis]: Checked inductivity of 315 backedges. 81 proven. 0 refuted. 0 times theorem prover too weak. 234 trivial. 0 not checked. [2022-03-18 19:36:12,015 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-18 19:36:12,015 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:36:12,015 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1985086889] [2022-03-18 19:36:12,015 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 19:36:12,015 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [552330247] [2022-03-18 19:36:12,015 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [552330247] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-18 19:36:12,015 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-18 19:36:12,016 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-18 19:36:12,016 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1537223616] [2022-03-18 19:36:12,016 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-18 19:36:12,016 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-18 19:36:12,016 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:36:12,016 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-18 19:36:12,017 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-03-18 19:36:12,017 INFO L87 Difference]: Start difference. First operand 102 states and 126 transitions. Second operand has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-03-18 19:36:12,058 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:36:12,058 INFO L93 Difference]: Finished difference Result 104 states and 127 transitions. [2022-03-18 19:36:12,058 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-18 19:36:12,059 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 95 [2022-03-18 19:36:12,059 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:36:12,059 INFO L225 Difference]: With dead ends: 104 [2022-03-18 19:36:12,060 INFO L226 Difference]: Without dead ends: 104 [2022-03-18 19:36:12,060 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-03-18 19:36:12,060 INFO L912 BasicCegarLoop]: 57 mSDtfsCounter, 9 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-18 19:36:12,061 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 129 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-18 19:36:12,061 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2022-03-18 19:36:12,065 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 104. [2022-03-18 19:36:12,065 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 104 states, 61 states have (on average 1.1311475409836065) internal successors, (69), 64 states have internal predecessors, (69), 30 states have call successors, (30), 13 states have call predecessors, (30), 12 states have return successors, (28), 26 states have call predecessors, (28), 28 states have call successors, (28) [2022-03-18 19:36:12,066 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 104 states to 104 states and 127 transitions. [2022-03-18 19:36:12,066 INFO L78 Accepts]: Start accepts. Automaton has 104 states and 127 transitions. Word has length 95 [2022-03-18 19:36:12,066 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:36:12,066 INFO L478 AbstractCegarLoop]: Abstraction has 104 states and 127 transitions. [2022-03-18 19:36:12,066 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.8) internal successors, (24), 5 states have internal predecessors, (24), 5 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2022-03-18 19:36:12,067 INFO L276 IsEmpty]: Start isEmpty. Operand 104 states and 127 transitions. [2022-03-18 19:36:12,067 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2022-03-18 19:36:12,067 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:36:12,068 INFO L500 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-18 19:36:12,094 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-03-18 19:36:12,287 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:36:12,287 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:36:12,287 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:36:12,287 INFO L85 PathProgramCache]: Analyzing trace with hash -317970408, now seen corresponding path program 3 times [2022-03-18 19:36:12,288 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:36:12,288 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1857437636] [2022-03-18 19:36:12,288 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:36:12,288 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:36:12,298 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 19:36:12,298 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1402444284] [2022-03-18 19:36:12,298 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-18 19:36:12,298 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:36:12,299 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 19:36:12,302 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 19:36:12,304 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-03-18 19:36:12,375 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-18 19:36:12,375 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 19:36:12,376 INFO L263 TraceCheckSpWp]: Trace formula consists of 194 conjuncts, 45 conjunts are in the unsatisfiable core [2022-03-18 19:36:12,379 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 19:36:13,107 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 37 proven. 55 refuted. 0 times theorem prover too weak. 282 trivial. 0 not checked. [2022-03-18 19:36:13,108 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 19:36:59,887 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 31 proven. 55 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2022-03-18 19:36:59,887 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:36:59,887 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1857437636] [2022-03-18 19:36:59,887 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 19:36:59,887 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1402444284] [2022-03-18 19:36:59,888 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1402444284] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 19:36:59,888 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 19:36:59,888 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 23 [2022-03-18 19:36:59,888 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [702898583] [2022-03-18 19:36:59,888 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 19:36:59,888 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-03-18 19:36:59,889 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:36:59,889 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-03-18 19:36:59,889 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=85, Invalid=421, Unknown=0, NotChecked=0, Total=506 [2022-03-18 19:36:59,889 INFO L87 Difference]: Start difference. First operand 104 states and 127 transitions. Second operand has 23 states, 23 states have (on average 2.130434782608696) internal successors, (49), 20 states have internal predecessors, (49), 11 states have call successors, (33), 2 states have call predecessors, (33), 3 states have return successors, (31), 11 states have call predecessors, (31), 9 states have call successors, (31) [2022-03-18 19:38:15,666 WARN L232 SmtUtils]: Spent 1.23m on a formula simplification. DAG size of input: 196 DAG size of output: 46 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 19:38:16,877 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.21s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 19:38:19,050 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 19:40:32,909 WARN L232 SmtUtils]: Spent 2.21m on a formula simplification. DAG size of input: 172 DAG size of output: 164 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 19:41:44,438 WARN L232 SmtUtils]: Spent 1.18m on a formula simplification. DAG size of input: 195 DAG size of output: 47 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 19:41:46,662 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 19:41:53,432 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 19:43:28,212 WARN L232 SmtUtils]: Spent 1.54m on a formula simplification. DAG size of input: 181 DAG size of output: 110 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 19:43:46,787 WARN L232 SmtUtils]: Spent 11.82s on a formula simplification. DAG size of input: 85 DAG size of output: 29 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 19:43:59,339 WARN L232 SmtUtils]: Spent 10.71s on a formula simplification. DAG size of input: 84 DAG size of output: 27 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 19:44:03,362 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 19:44:12,745 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-18 19:44:13,220 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:44:13,220 INFO L93 Difference]: Finished difference Result 199 states and 258 transitions. [2022-03-18 19:44:13,221 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2022-03-18 19:44:13,221 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.130434782608696) internal successors, (49), 20 states have internal predecessors, (49), 11 states have call successors, (33), 2 states have call predecessors, (33), 3 states have return successors, (31), 11 states have call predecessors, (31), 9 states have call successors, (31) Word has length 105 [2022-03-18 19:44:13,222 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:44:13,223 INFO L225 Difference]: With dead ends: 199 [2022-03-18 19:44:13,223 INFO L226 Difference]: Without dead ends: 183 [2022-03-18 19:44:13,223 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 227 GetRequests, 184 SyntacticMatches, 4 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 333 ImplicationChecksByTransitivity, 418.0s TimeCoverageRelationStatistics Valid=282, Invalid=1356, Unknown=2, NotChecked=0, Total=1640 [2022-03-18 19:44:13,224 INFO L912 BasicCegarLoop]: 50 mSDtfsCounter, 114 mSDsluCounter, 524 mSDsCounter, 0 mSdLazyCounter, 958 mSolverCounterSat, 304 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 23.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 127 SdHoareTripleChecker+Valid, 574 SdHoareTripleChecker+Invalid, 1267 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 304 IncrementalHoareTripleChecker+Valid, 958 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 23.7s IncrementalHoareTripleChecker+Time [2022-03-18 19:44:13,224 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [127 Valid, 574 Invalid, 1267 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [304 Valid, 958 Invalid, 5 Unknown, 0 Unchecked, 23.7s Time] [2022-03-18 19:44:13,225 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2022-03-18 19:44:13,230 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 161. [2022-03-18 19:44:13,230 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 161 states, 96 states have (on average 1.125) internal successors, (108), 103 states have internal predecessors, (108), 46 states have call successors, (46), 19 states have call predecessors, (46), 18 states have return successors, (44), 38 states have call predecessors, (44), 44 states have call successors, (44) [2022-03-18 19:44:13,231 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 161 states to 161 states and 198 transitions. [2022-03-18 19:44:13,231 INFO L78 Accepts]: Start accepts. Automaton has 161 states and 198 transitions. Word has length 105 [2022-03-18 19:44:13,232 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:44:13,232 INFO L478 AbstractCegarLoop]: Abstraction has 161 states and 198 transitions. [2022-03-18 19:44:13,232 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.130434782608696) internal successors, (49), 20 states have internal predecessors, (49), 11 states have call successors, (33), 2 states have call predecessors, (33), 3 states have return successors, (31), 11 states have call predecessors, (31), 9 states have call successors, (31) [2022-03-18 19:44:13,232 INFO L276 IsEmpty]: Start isEmpty. Operand 161 states and 198 transitions. [2022-03-18 19:44:13,233 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2022-03-18 19:44:13,233 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:44:13,233 INFO L500 BasicCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2022-03-18 19:44:13,258 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-03-18 19:44:13,453 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-03-18 19:44:13,454 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:44:13,454 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:44:13,454 INFO L85 PathProgramCache]: Analyzing trace with hash -1498631042, now seen corresponding path program 2 times [2022-03-18 19:44:13,454 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:44:13,454 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1395862866] [2022-03-18 19:44:13,454 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:44:13,454 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:44:13,466 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 19:44:13,466 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1751779063] [2022-03-18 19:44:13,466 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-18 19:44:13,466 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:44:13,466 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 19:44:13,471 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 19:44:13,471 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-03-18 19:44:13,578 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-18 19:44:13,578 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 19:44:13,579 INFO L263 TraceCheckSpWp]: Trace formula consists of 261 conjuncts, 49 conjunts are in the unsatisfiable core [2022-03-18 19:44:13,581 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 19:44:14,551 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-18 19:44:15,432 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 106 proven. 30 refuted. 0 times theorem prover too weak. 354 trivial. 0 not checked. [2022-03-18 19:44:15,432 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 19:44:16,023 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 110 proven. 2 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2022-03-18 19:44:16,023 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-18 19:44:16,023 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1395862866] [2022-03-18 19:44:16,023 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-18 19:44:16,023 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1751779063] [2022-03-18 19:44:16,023 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1751779063] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-18 19:44:16,024 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-18 19:44:16,024 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 9] total 20 [2022-03-18 19:44:16,024 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [551808684] [2022-03-18 19:44:16,024 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-18 19:44:16,024 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-03-18 19:44:16,024 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-18 19:44:16,025 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-03-18 19:44:16,025 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=302, Unknown=0, NotChecked=0, Total=380 [2022-03-18 19:44:16,025 INFO L87 Difference]: Start difference. First operand 161 states and 198 transitions. Second operand has 20 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 10 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 8 states have call successors, (26) [2022-03-18 19:44:17,249 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-18 19:44:17,249 INFO L93 Difference]: Finished difference Result 187 states and 226 transitions. [2022-03-18 19:44:17,250 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-03-18 19:44:17,250 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 10 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 8 states have call successors, (26) Word has length 116 [2022-03-18 19:44:17,250 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-18 19:44:17,251 INFO L225 Difference]: With dead ends: 187 [2022-03-18 19:44:17,251 INFO L226 Difference]: Without dead ends: 159 [2022-03-18 19:44:17,251 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 233 GetRequests, 211 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=91, Invalid=371, Unknown=0, NotChecked=0, Total=462 [2022-03-18 19:44:17,252 INFO L912 BasicCegarLoop]: 45 mSDtfsCounter, 36 mSDsluCounter, 277 mSDsCounter, 0 mSdLazyCounter, 460 mSolverCounterSat, 69 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 322 SdHoareTripleChecker+Invalid, 529 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 69 IncrementalHoareTripleChecker+Valid, 460 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2022-03-18 19:44:17,252 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [49 Valid, 322 Invalid, 529 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [69 Valid, 460 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2022-03-18 19:44:17,253 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 159 states. [2022-03-18 19:44:17,258 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 159 to 138. [2022-03-18 19:44:17,258 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 84 states have (on average 1.1071428571428572) internal successors, (93), 89 states have internal predecessors, (93), 35 states have call successors, (35), 19 states have call predecessors, (35), 18 states have return successors, (33), 29 states have call predecessors, (33), 33 states have call successors, (33) [2022-03-18 19:44:17,259 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 161 transitions. [2022-03-18 19:44:17,259 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 161 transitions. Word has length 116 [2022-03-18 19:44:17,259 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-18 19:44:17,259 INFO L478 AbstractCegarLoop]: Abstraction has 138 states and 161 transitions. [2022-03-18 19:44:17,259 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 17 states have (on average 2.411764705882353) internal successors, (41), 16 states have internal predecessors, (41), 10 states have call successors, (28), 2 states have call predecessors, (28), 2 states have return successors, (26), 10 states have call predecessors, (26), 8 states have call successors, (26) [2022-03-18 19:44:17,260 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 161 transitions. [2022-03-18 19:44:17,261 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2022-03-18 19:44:17,261 INFO L492 BasicCegarLoop]: Found error trace [2022-03-18 19:44:17,261 INFO L500 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 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-03-18 19:44:17,285 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-03-18 19:44:17,485 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-03-18 19:44:17,486 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-18 19:44:17,486 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-18 19:44:17,486 INFO L85 PathProgramCache]: Analyzing trace with hash -715358301, now seen corresponding path program 4 times [2022-03-18 19:44:17,486 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-18 19:44:17,486 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1342088032] [2022-03-18 19:44:17,486 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-18 19:44:17,487 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-18 19:44:17,494 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-18 19:44:17,495 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [247118183] [2022-03-18 19:44:17,495 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-18 19:44:17,495 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-18 19:44:17,495 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-18 19:44:17,496 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-18 19:44:17,497 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-03-18 19:44:17,565 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-18 19:44:17,565 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-18 19:44:17,566 INFO L263 TraceCheckSpWp]: Trace formula consists of 303 conjuncts, 51 conjunts are in the unsatisfiable core [2022-03-18 19:44:17,569 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-18 19:44:18,696 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 36 proven. 51 refuted. 0 times theorem prover too weak. 624 trivial. 0 not checked. [2022-03-18 19:44:18,696 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-18 19:44:41,274 WARN L232 SmtUtils]: Spent 6.01s on a formula simplification that was a NOOP. DAG size: 147 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 19:45:15,377 WARN L232 SmtUtils]: Spent 5.43s on a formula simplification that was a NOOP. DAG size: 150 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-18 19:46:20,688 WARN L232 SmtUtils]: Spent 21.68s on a formula simplification that was a NOOP. DAG size: 451 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate)