/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/divbin2_unwindbound50.i -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-6c470ae [2022-02-14 22:22:29,843 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-02-14 22:22:29,845 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-02-14 22:22:29,901 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-02-14 22:22:29,901 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-02-14 22:22:29,903 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-02-14 22:22:29,904 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-02-14 22:22:29,905 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-02-14 22:22:29,907 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-02-14 22:22:29,908 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-02-14 22:22:29,909 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-02-14 22:22:29,910 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-02-14 22:22:29,910 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-02-14 22:22:29,911 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-02-14 22:22:29,912 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-02-14 22:22:29,913 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-02-14 22:22:29,913 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-02-14 22:22:29,914 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-02-14 22:22:29,915 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-02-14 22:22:29,917 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-02-14 22:22:29,918 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-02-14 22:22:29,922 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-02-14 22:22:29,923 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-02-14 22:22:29,923 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-02-14 22:22:29,926 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-02-14 22:22:29,926 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-02-14 22:22:29,926 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-02-14 22:22:29,927 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-02-14 22:22:29,927 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-02-14 22:22:29,928 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-02-14 22:22:29,928 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-02-14 22:22:29,929 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-02-14 22:22:29,929 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-02-14 22:22:29,930 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-02-14 22:22:29,931 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-02-14 22:22:29,931 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-02-14 22:22:29,931 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-02-14 22:22:29,931 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-02-14 22:22:29,931 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-02-14 22:22:29,932 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-02-14 22:22:29,932 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-02-14 22:22:29,936 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-02-14 22:22:29,944 INFO L113 SettingsManager]: Loading preferences was successful [2022-02-14 22:22:29,944 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-02-14 22:22:29,945 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-02-14 22:22:29,945 INFO L138 SettingsManager]: * sizeof long=4 [2022-02-14 22:22:29,945 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-02-14 22:22:29,945 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-02-14 22:22:29,946 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-02-14 22:22:29,946 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-02-14 22:22:29,946 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-02-14 22:22:29,946 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-02-14 22:22:29,946 INFO L138 SettingsManager]: * sizeof long double=12 [2022-02-14 22:22:29,946 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-02-14 22:22:29,946 INFO L138 SettingsManager]: * Use constant arrays=true [2022-02-14 22:22:29,946 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-02-14 22:22:29,947 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-02-14 22:22:29,947 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-02-14 22:22:29,947 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-02-14 22:22:29,947 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-02-14 22:22:29,947 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-02-14 22:22:29,947 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-02-14 22:22:29,947 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-02-14 22:22:29,948 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-02-14 22:22:29,948 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-02-14 22:22:30,152 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-02-14 22:22:30,170 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-02-14 22:22:30,172 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-02-14 22:22:30,172 INFO L271 PluginConnector]: Initializing CDTParser... [2022-02-14 22:22:30,173 INFO L275 PluginConnector]: CDTParser initialized [2022-02-14 22:22:30,174 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/divbin2_unwindbound50.i [2022-02-14 22:22:30,228 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/022ba16d3/ffecb9b12c5b478fb74215003ecaece2/FLAGf5bc2adf8 [2022-02-14 22:22:30,553 INFO L306 CDTParser]: Found 1 translation units. [2022-02-14 22:22:30,554 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/divbin2_unwindbound50.i [2022-02-14 22:22:30,567 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/022ba16d3/ffecb9b12c5b478fb74215003ecaece2/FLAGf5bc2adf8 [2022-02-14 22:22:30,991 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/022ba16d3/ffecb9b12c5b478fb74215003ecaece2 [2022-02-14 22:22:30,995 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-02-14 22:22:30,997 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-02-14 22:22:30,998 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-02-14 22:22:30,998 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-02-14 22:22:31,001 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-02-14 22:22:31,001 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.02 10:22:30" (1/1) ... [2022-02-14 22:22:31,003 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2e4906de and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.02 10:22:31, skipping insertion in model container [2022-02-14 22:22:31,003 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.02 10:22:30" (1/1) ... [2022-02-14 22:22:31,010 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-02-14 22:22:31,023 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-02-14 22:22:31,180 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/divbin2_unwindbound50.i[951,964] [2022-02-14 22:22:31,199 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-02-14 22:22:31,207 INFO L203 MainTranslator]: Completed pre-run [2022-02-14 22:22:31,228 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/divbin2_unwindbound50.i[951,964] [2022-02-14 22:22:31,246 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-02-14 22:22:31,258 INFO L208 MainTranslator]: Completed translation [2022-02-14 22:22:31,259 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.02 10:22:31 WrapperNode [2022-02-14 22:22:31,259 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-02-14 22:22:31,260 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-02-14 22:22:31,260 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-02-14 22:22:31,260 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-02-14 22:22:31,271 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.02 10:22:31" (1/1) ... [2022-02-14 22:22:31,271 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.02 10:22:31" (1/1) ... [2022-02-14 22:22:31,278 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.02 10:22:31" (1/1) ... [2022-02-14 22:22:31,278 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.02 10:22:31" (1/1) ... [2022-02-14 22:22:31,291 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.02 10:22:31" (1/1) ... [2022-02-14 22:22:31,295 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.02 10:22:31" (1/1) ... [2022-02-14 22:22:31,296 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.02 10:22:31" (1/1) ... [2022-02-14 22:22:31,297 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-02-14 22:22:31,298 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-02-14 22:22:31,298 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-02-14 22:22:31,298 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-02-14 22:22:31,299 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.02 10:22:31" (1/1) ... [2022-02-14 22:22:31,307 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-02-14 22:22:31,319 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-14 22:22:31,337 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-02-14 22:22:31,362 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-02-14 22:22:31,385 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-02-14 22:22:31,385 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-02-14 22:22:31,385 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-02-14 22:22:31,385 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-02-14 22:22:31,386 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-02-14 22:22:31,386 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-02-14 22:22:31,386 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-02-14 22:22:31,386 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-02-14 22:22:31,386 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_perror_fail [2022-02-14 22:22:31,387 INFO L130 BoogieDeclarations]: Found specification of procedure __assert [2022-02-14 22:22:31,387 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-02-14 22:22:31,387 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-02-14 22:22:31,387 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-02-14 22:22:31,387 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-02-14 22:22:31,387 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-02-14 22:22:31,388 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-02-14 22:22:31,390 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-02-14 22:22:31,390 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-02-14 22:22:31,390 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-02-14 22:22:31,390 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-02-14 22:22:31,390 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-02-14 22:22:31,390 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-02-14 22:22:31,480 INFO L234 CfgBuilder]: Building ICFG [2022-02-14 22:22:31,481 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-02-14 22:22:31,604 INFO L275 CfgBuilder]: Performing block encoding [2022-02-14 22:22:31,610 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-02-14 22:22:31,610 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-02-14 22:22:31,611 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.02 10:22:31 BoogieIcfgContainer [2022-02-14 22:22:31,611 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-02-14 22:22:31,612 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-02-14 22:22:31,612 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-02-14 22:22:31,613 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-02-14 22:22:31,622 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.02 10:22:31" (1/1) ... [2022-02-14 22:22:31,651 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 14.02 10:22:31 BasicIcfg [2022-02-14 22:22:31,652 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-02-14 22:22:31,653 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-02-14 22:22:31,653 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-02-14 22:22:31,669 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-02-14 22:22:31,670 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.02 10:22:30" (1/4) ... [2022-02-14 22:22:31,670 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6200a4c0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.02 10:22:31, skipping insertion in model container [2022-02-14 22:22:31,671 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.02 10:22:31" (2/4) ... [2022-02-14 22:22:31,671 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6200a4c0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.02 10:22:31, skipping insertion in model container [2022-02-14 22:22:31,671 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.02 10:22:31" (3/4) ... [2022-02-14 22:22:31,671 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6200a4c0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 14.02 10:22:31, skipping insertion in model container [2022-02-14 22:22:31,671 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 14.02 10:22:31" (4/4) ... [2022-02-14 22:22:31,672 INFO L111 eAbstractionObserver]: Analyzing ICFG divbin2_unwindbound50.iJordan [2022-02-14 22:22:31,677 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-02-14 22:22:31,677 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-02-14 22:22:31,723 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-02-14 22:22:31,733 INFO L339 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, mLoopAccelerationTechnique=FAST_UPR [2022-02-14 22:22:31,733 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-02-14 22:22:31,748 INFO L276 IsEmpty]: Start isEmpty. Operand has 26 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-02-14 22:22:31,754 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-02-14 22:22:31,755 INFO L506 BasicCegarLoop]: Found error trace [2022-02-14 22:22:31,755 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-14 22:22:31,756 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-14 22:22:31,760 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-14 22:22:31,760 INFO L85 PathProgramCache]: Analyzing trace with hash 2097950667, now seen corresponding path program 1 times [2022-02-14 22:22:31,779 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-14 22:22:31,780 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [264045697] [2022-02-14 22:22:31,781 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:31,781 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-14 22:22:31,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-14 22:22:31,900 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-02-14 22:22:31,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-14 22:22:31,911 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-14 22:22:31,912 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-14 22:22:31,912 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [264045697] [2022-02-14 22:22:31,913 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [264045697] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-14 22:22:31,913 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-14 22:22:31,913 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-02-14 22:22:31,915 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [944290001] [2022-02-14 22:22:31,915 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-14 22:22:31,919 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-02-14 22:22:31,920 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-14 22:22:31,942 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-02-14 22:22:31,943 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-02-14 22:22:31,944 INFO L87 Difference]: Start difference. First operand has 26 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-14 22:22:31,994 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-14 22:22:31,994 INFO L93 Difference]: Finished difference Result 27 states and 32 transitions. [2022-02-14 22:22:32,002 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-02-14 22:22:32,004 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-02-14 22:22:32,004 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-14 22:22:32,010 INFO L225 Difference]: With dead ends: 27 [2022-02-14 22:22:32,011 INFO L226 Difference]: Without dead ends: 22 [2022-02-14 22:22:32,016 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-02-14 22:22:32,019 INFO L933 BasicCegarLoop]: 30 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-14 22:22:32,020 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 34 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 18 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-14 22:22:32,040 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2022-02-14 22:22:32,061 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 21. [2022-02-14 22:22:32,062 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-02-14 22:22:32,063 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 26 transitions. [2022-02-14 22:22:32,063 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 26 transitions. Word has length 12 [2022-02-14 22:22:32,064 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-14 22:22:32,064 INFO L470 AbstractCegarLoop]: Abstraction has 21 states and 26 transitions. [2022-02-14 22:22:32,064 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-14 22:22:32,064 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 26 transitions. [2022-02-14 22:22:32,065 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-02-14 22:22:32,065 INFO L506 BasicCegarLoop]: Found error trace [2022-02-14 22:22:32,065 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-14 22:22:32,065 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-02-14 22:22:32,066 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-14 22:22:32,066 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-14 22:22:32,067 INFO L85 PathProgramCache]: Analyzing trace with hash 923003056, now seen corresponding path program 1 times [2022-02-14 22:22:32,067 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-14 22:22:32,067 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [920784449] [2022-02-14 22:22:32,067 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:32,067 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-14 22:22:32,086 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-14 22:22:32,128 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-02-14 22:22:32,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-14 22:22:32,161 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-14 22:22:32,162 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-14 22:22:32,162 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [920784449] [2022-02-14 22:22:32,162 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [920784449] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-14 22:22:32,162 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-14 22:22:32,163 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-02-14 22:22:32,163 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [969005700] [2022-02-14 22:22:32,163 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-14 22:22:32,164 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-14 22:22:32,165 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-14 22:22:32,165 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-14 22:22:32,166 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-02-14 22:22:32,166 INFO L87 Difference]: Start difference. First operand 21 states and 26 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-14 22:22:32,249 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-14 22:22:32,249 INFO L93 Difference]: Finished difference Result 23 states and 28 transitions. [2022-02-14 22:22:32,249 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-02-14 22:22:32,250 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-02-14 22:22:32,250 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-14 22:22:32,250 INFO L225 Difference]: With dead ends: 23 [2022-02-14 22:22:32,251 INFO L226 Difference]: Without dead ends: 23 [2022-02-14 22:22:32,251 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-02-14 22:22:32,252 INFO L933 BasicCegarLoop]: 24 mSDtfsCounter, 6 mSDsluCounter, 29 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-14 22:22:32,253 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 53 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-14 22:22:32,254 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2022-02-14 22:22:32,256 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2022-02-14 22:22:32,257 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-02-14 22:22:32,257 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 28 transitions. [2022-02-14 22:22:32,257 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 28 transitions. Word has length 14 [2022-02-14 22:22:32,258 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-14 22:22:32,258 INFO L470 AbstractCegarLoop]: Abstraction has 23 states and 28 transitions. [2022-02-14 22:22:32,258 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-14 22:22:32,258 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 28 transitions. [2022-02-14 22:22:32,259 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2022-02-14 22:22:32,259 INFO L506 BasicCegarLoop]: Found error trace [2022-02-14 22:22:32,260 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-14 22:22:32,260 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-02-14 22:22:32,260 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-14 22:22:32,261 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-14 22:22:32,261 INFO L85 PathProgramCache]: Analyzing trace with hash 1207414063, now seen corresponding path program 1 times [2022-02-14 22:22:32,261 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-14 22:22:32,261 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1016368757] [2022-02-14 22:22:32,261 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:32,262 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-14 22:22:32,284 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-14 22:22:32,284 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1329580226] [2022-02-14 22:22:32,285 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:32,285 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:32,285 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-14 22:22:32,291 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-02-14 22:22:32,294 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-02-14 22:22:32,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-14 22:22:32,338 INFO L263 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 7 conjunts are in the unsatisfiable core [2022-02-14 22:22:32,343 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-14 22:22:32,421 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-14 22:22:32,421 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-14 22:22:32,422 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-14 22:22:32,422 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1016368757] [2022-02-14 22:22:32,422 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-14 22:22:32,422 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1329580226] [2022-02-14 22:22:32,422 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1329580226] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-14 22:22:32,423 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-14 22:22:32,423 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-02-14 22:22:32,423 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [204242480] [2022-02-14 22:22:32,423 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-14 22:22:32,424 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-14 22:22:32,424 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-14 22:22:32,424 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-14 22:22:32,424 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-02-14 22:22:32,425 INFO L87 Difference]: Start difference. First operand 23 states and 28 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-14 22:22:32,441 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-14 22:22:32,442 INFO L93 Difference]: Finished difference Result 27 states and 33 transitions. [2022-02-14 22:22:32,442 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-14 22:22:32,442 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2022-02-14 22:22:32,442 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-14 22:22:32,443 INFO L225 Difference]: With dead ends: 27 [2022-02-14 22:22:32,443 INFO L226 Difference]: Without dead ends: 27 [2022-02-14 22:22:32,443 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-02-14 22:22:32,444 INFO L933 BasicCegarLoop]: 23 mSDtfsCounter, 3 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-14 22:22:32,445 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 81 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-14 22:22:32,446 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-02-14 22:22:32,448 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-02-14 22:22:32,448 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 19 states have (on average 1.368421052631579) internal successors, (26), 20 states have internal predecessors, (26), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-02-14 22:22:32,449 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 32 transitions. [2022-02-14 22:22:32,449 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 32 transitions. Word has length 15 [2022-02-14 22:22:32,449 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-14 22:22:32,449 INFO L470 AbstractCegarLoop]: Abstraction has 26 states and 32 transitions. [2022-02-14 22:22:32,450 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-14 22:22:32,450 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 32 transitions. [2022-02-14 22:22:32,450 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2022-02-14 22:22:32,450 INFO L506 BasicCegarLoop]: Found error trace [2022-02-14 22:22:32,450 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-14 22:22:32,475 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-02-14 22:22:32,675 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:32,675 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-14 22:22:32,676 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-14 22:22:32,676 INFO L85 PathProgramCache]: Analyzing trace with hash 1208546121, now seen corresponding path program 1 times [2022-02-14 22:22:32,676 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-14 22:22:32,677 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1455062131] [2022-02-14 22:22:32,677 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:32,677 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-14 22:22:32,692 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-14 22:22:32,693 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1342373694] [2022-02-14 22:22:32,693 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:32,693 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:32,693 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-14 22:22:32,698 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-02-14 22:22:32,701 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-02-14 22:22:32,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-14 22:22:32,753 INFO L263 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 14 conjunts are in the unsatisfiable core [2022-02-14 22:22:32,755 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-14 22:22:32,880 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-14 22:22:32,880 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-14 22:22:32,880 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-14 22:22:32,880 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1455062131] [2022-02-14 22:22:32,881 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-14 22:22:32,881 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1342373694] [2022-02-14 22:22:32,881 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1342373694] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-14 22:22:32,881 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-14 22:22:32,881 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-02-14 22:22:32,881 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1130174160] [2022-02-14 22:22:32,882 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-14 22:22:32,882 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-02-14 22:22:32,882 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-14 22:22:32,883 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-02-14 22:22:32,883 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2022-02-14 22:22:32,883 INFO L87 Difference]: Start difference. First operand 26 states and 32 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 5 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-14 22:22:32,936 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-14 22:22:32,936 INFO L93 Difference]: Finished difference Result 33 states and 40 transitions. [2022-02-14 22:22:32,936 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-02-14 22:22:32,937 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 5 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2022-02-14 22:22:32,937 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-14 22:22:32,940 INFO L225 Difference]: With dead ends: 33 [2022-02-14 22:22:32,940 INFO L226 Difference]: Without dead ends: 32 [2022-02-14 22:22:32,941 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2022-02-14 22:22:32,944 INFO L933 BasicCegarLoop]: 21 mSDtfsCounter, 9 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-14 22:22:32,946 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 96 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-14 22:22:32,947 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-02-14 22:22:32,955 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-02-14 22:22:32,955 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-02-14 22:22:32,958 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 38 transitions. [2022-02-14 22:22:32,959 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 38 transitions. Word has length 15 [2022-02-14 22:22:32,959 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-14 22:22:32,959 INFO L470 AbstractCegarLoop]: Abstraction has 32 states and 38 transitions. [2022-02-14 22:22:32,960 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 5 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-14 22:22:32,960 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 38 transitions. [2022-02-14 22:22:32,962 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-02-14 22:22:32,962 INFO L506 BasicCegarLoop]: Found error trace [2022-02-14 22:22:32,962 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-14 22:22:32,993 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-02-14 22:22:33,182 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2022-02-14 22:22:33,182 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-14 22:22:33,183 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-14 22:22:33,183 INFO L85 PathProgramCache]: Analyzing trace with hash 1227316531, now seen corresponding path program 1 times [2022-02-14 22:22:33,183 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-14 22:22:33,183 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [463371613] [2022-02-14 22:22:33,184 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:33,184 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-14 22:22:33,196 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-14 22:22:33,196 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [480270825] [2022-02-14 22:22:33,197 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:33,199 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:33,199 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-14 22:22:33,203 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-02-14 22:22:33,205 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-02-14 22:22:33,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-14 22:22:33,244 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 7 conjunts are in the unsatisfiable core [2022-02-14 22:22:33,246 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-14 22:22:33,297 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-14 22:22:33,298 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-14 22:22:33,365 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-14 22:22:33,366 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-14 22:22:33,366 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [463371613] [2022-02-14 22:22:33,366 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-14 22:22:33,366 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [480270825] [2022-02-14 22:22:33,366 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [480270825] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-14 22:22:33,366 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-14 22:22:33,366 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-02-14 22:22:33,366 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [696914442] [2022-02-14 22:22:33,367 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-14 22:22:33,367 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-02-14 22:22:33,367 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-14 22:22:33,368 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-02-14 22:22:33,368 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-02-14 22:22:33,368 INFO L87 Difference]: Start difference. First operand 32 states and 38 transitions. Second operand has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-02-14 22:22:33,433 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-14 22:22:33,434 INFO L93 Difference]: Finished difference Result 54 states and 66 transitions. [2022-02-14 22:22:33,434 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-02-14 22:22:33,434 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-02-14 22:22:33,435 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-14 22:22:33,436 INFO L225 Difference]: With dead ends: 54 [2022-02-14 22:22:33,437 INFO L226 Difference]: Without dead ends: 54 [2022-02-14 22:22:33,437 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-02-14 22:22:33,438 INFO L933 BasicCegarLoop]: 25 mSDtfsCounter, 31 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-14 22:22:33,438 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 94 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-14 22:22:33,439 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-02-14 22:22:33,442 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 40. [2022-02-14 22:22:33,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 31 states have (on average 1.2903225806451613) internal successors, (40), 32 states have internal predecessors, (40), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-02-14 22:22:33,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 48 transitions. [2022-02-14 22:22:33,443 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 48 transitions. Word has length 17 [2022-02-14 22:22:33,443 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-14 22:22:33,443 INFO L470 AbstractCegarLoop]: Abstraction has 40 states and 48 transitions. [2022-02-14 22:22:33,444 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-02-14 22:22:33,444 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 48 transitions. [2022-02-14 22:22:33,444 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-02-14 22:22:33,444 INFO L506 BasicCegarLoop]: Found error trace [2022-02-14 22:22:33,445 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-14 22:22:33,467 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-02-14 22:22:33,653 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:33,653 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-14 22:22:33,654 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-14 22:22:33,654 INFO L85 PathProgramCache]: Analyzing trace with hash 2051197196, now seen corresponding path program 1 times [2022-02-14 22:22:33,654 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-14 22:22:33,654 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [330381136] [2022-02-14 22:22:33,654 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:33,654 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-14 22:22:33,666 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-14 22:22:33,666 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [971407076] [2022-02-14 22:22:33,666 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:33,666 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:33,667 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-14 22:22:33,668 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-02-14 22:22:33,691 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-02-14 22:22:33,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-14 22:22:33,714 INFO L263 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 9 conjunts are in the unsatisfiable core [2022-02-14 22:22:33,716 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-14 22:22:33,793 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-14 22:22:33,794 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-14 22:22:33,895 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-14 22:22:33,896 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-14 22:22:33,896 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [330381136] [2022-02-14 22:22:33,896 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-14 22:22:33,897 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [971407076] [2022-02-14 22:22:33,897 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [971407076] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-14 22:22:33,897 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-14 22:22:33,897 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2022-02-14 22:22:33,897 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [625890009] [2022-02-14 22:22:33,897 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-14 22:22:33,898 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-02-14 22:22:33,899 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-14 22:22:33,899 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-02-14 22:22:33,899 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-02-14 22:22:33,900 INFO L87 Difference]: Start difference. First operand 40 states and 48 transitions. Second operand has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-02-14 22:22:34,009 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-14 22:22:34,009 INFO L93 Difference]: Finished difference Result 84 states and 102 transitions. [2022-02-14 22:22:34,010 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-02-14 22:22:34,010 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-02-14 22:22:34,010 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-14 22:22:34,013 INFO L225 Difference]: With dead ends: 84 [2022-02-14 22:22:34,014 INFO L226 Difference]: Without dead ends: 84 [2022-02-14 22:22:34,014 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2022-02-14 22:22:34,017 INFO L933 BasicCegarLoop]: 27 mSDtfsCounter, 79 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 70 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-14 22:22:34,017 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [79 Valid, 136 Invalid, 70 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-14 22:22:34,018 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2022-02-14 22:22:34,028 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 77. [2022-02-14 22:22:34,029 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 59 states have (on average 1.3728813559322033) internal successors, (81), 63 states have internal predecessors, (81), 11 states have call successors, (11), 7 states have call predecessors, (11), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-02-14 22:22:34,030 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 98 transitions. [2022-02-14 22:22:34,031 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 98 transitions. Word has length 18 [2022-02-14 22:22:34,031 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-14 22:22:34,031 INFO L470 AbstractCegarLoop]: Abstraction has 77 states and 98 transitions. [2022-02-14 22:22:34,031 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-02-14 22:22:34,031 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 98 transitions. [2022-02-14 22:22:34,032 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-02-14 22:22:34,032 INFO L506 BasicCegarLoop]: Found error trace [2022-02-14 22:22:34,032 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-14 22:22:34,058 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-02-14 22:22:34,245 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:34,245 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-14 22:22:34,246 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-14 22:22:34,246 INFO L85 PathProgramCache]: Analyzing trace with hash 2052329254, now seen corresponding path program 1 times [2022-02-14 22:22:34,246 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-14 22:22:34,246 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1756295531] [2022-02-14 22:22:34,246 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:34,247 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-14 22:22:34,258 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-14 22:22:34,259 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [90972395] [2022-02-14 22:22:34,259 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:34,259 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:34,259 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-14 22:22:34,260 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-02-14 22:22:34,271 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-02-14 22:22:34,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-14 22:22:34,332 INFO L263 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 14 conjunts are in the unsatisfiable core [2022-02-14 22:22:34,336 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-14 22:22:34,468 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-14 22:22:34,469 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-14 22:22:34,685 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-14 22:22:34,686 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-14 22:22:34,686 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1756295531] [2022-02-14 22:22:34,686 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-14 22:22:34,686 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [90972395] [2022-02-14 22:22:34,686 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [90972395] provided 1 perfect and 1 imperfect interpolant sequences [2022-02-14 22:22:34,687 INFO L191 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-02-14 22:22:34,687 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 8 [2022-02-14 22:22:34,687 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [275898975] [2022-02-14 22:22:34,687 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-14 22:22:34,687 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-02-14 22:22:34,688 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-14 22:22:34,688 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-02-14 22:22:34,688 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2022-02-14 22:22:34,688 INFO L87 Difference]: Start difference. First operand 77 states and 98 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-14 22:22:34,706 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-14 22:22:34,706 INFO L93 Difference]: Finished difference Result 108 states and 130 transitions. [2022-02-14 22:22:34,708 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-02-14 22:22:34,708 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 18 [2022-02-14 22:22:34,708 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-14 22:22:34,710 INFO L225 Difference]: With dead ends: 108 [2022-02-14 22:22:34,711 INFO L226 Difference]: Without dead ends: 108 [2022-02-14 22:22:34,711 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 28 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-02-14 22:22:34,712 INFO L933 BasicCegarLoop]: 31 mSDtfsCounter, 11 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 11 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-14 22:22:34,714 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 104 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 11 Unchecked, 0.0s Time] [2022-02-14 22:22:34,715 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2022-02-14 22:22:34,734 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 107. [2022-02-14 22:22:34,734 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 81 states have (on average 1.2839506172839505) internal successors, (104), 89 states have internal predecessors, (104), 15 states have call successors, (15), 11 states have call predecessors, (15), 10 states have return successors, (10), 6 states have call predecessors, (10), 10 states have call successors, (10) [2022-02-14 22:22:34,736 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 129 transitions. [2022-02-14 22:22:34,736 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 129 transitions. Word has length 18 [2022-02-14 22:22:34,736 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-14 22:22:34,736 INFO L470 AbstractCegarLoop]: Abstraction has 107 states and 129 transitions. [2022-02-14 22:22:34,736 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-02-14 22:22:34,736 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 129 transitions. [2022-02-14 22:22:34,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-02-14 22:22:34,737 INFO L506 BasicCegarLoop]: Found error trace [2022-02-14 22:22:34,737 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-14 22:22:34,763 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-02-14 22:22:34,938 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:34,938 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-14 22:22:34,938 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-14 22:22:34,939 INFO L85 PathProgramCache]: Analyzing trace with hash 462666167, now seen corresponding path program 1 times [2022-02-14 22:22:34,939 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-14 22:22:34,939 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1894119110] [2022-02-14 22:22:34,939 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:34,939 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-14 22:22:34,961 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-14 22:22:34,961 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [43991859] [2022-02-14 22:22:34,961 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:34,962 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:34,962 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-14 22:22:34,968 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-02-14 22:22:34,969 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-02-14 22:22:35,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-14 22:22:35,012 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 5 conjunts are in the unsatisfiable core [2022-02-14 22:22:35,015 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-14 22:22:35,087 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-14 22:22:35,087 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-14 22:22:35,087 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-14 22:22:35,087 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1894119110] [2022-02-14 22:22:35,087 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-14 22:22:35,088 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [43991859] [2022-02-14 22:22:35,088 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [43991859] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-14 22:22:35,088 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-14 22:22:35,088 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-02-14 22:22:35,088 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [509004825] [2022-02-14 22:22:35,088 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-14 22:22:35,089 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-02-14 22:22:35,089 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-14 22:22:35,089 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-02-14 22:22:35,089 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-02-14 22:22:35,089 INFO L87 Difference]: Start difference. First operand 107 states and 129 transitions. Second operand has 3 states, 3 states have (on average 6.0) internal successors, (18), 3 states have internal predecessors, (18), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-02-14 22:22:35,104 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-14 22:22:35,104 INFO L93 Difference]: Finished difference Result 103 states and 122 transitions. [2022-02-14 22:22:35,104 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-02-14 22:22:35,105 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 6.0) internal successors, (18), 3 states have internal predecessors, (18), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2022-02-14 22:22:35,105 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-14 22:22:35,106 INFO L225 Difference]: With dead ends: 103 [2022-02-14 22:22:35,106 INFO L226 Difference]: Without dead ends: 93 [2022-02-14 22:22:35,107 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 22 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-02-14 22:22:35,108 INFO L933 BasicCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 19 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-14 22:22:35,108 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 44 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-14 22:22:35,109 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-02-14 22:22:35,123 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-02-14 22:22:35,123 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 71 states have (on average 1.2816901408450705) internal successors, (91), 77 states have internal predecessors, (91), 13 states have call successors, (13), 10 states have call predecessors, (13), 8 states have return successors, (8), 5 states have call predecessors, (8), 8 states have call successors, (8) [2022-02-14 22:22:35,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 112 transitions. [2022-02-14 22:22:35,127 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 112 transitions. Word has length 24 [2022-02-14 22:22:35,128 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-14 22:22:35,128 INFO L470 AbstractCegarLoop]: Abstraction has 93 states and 112 transitions. [2022-02-14 22:22:35,128 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 6.0) internal successors, (18), 3 states have internal predecessors, (18), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-02-14 22:22:35,128 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 112 transitions. [2022-02-14 22:22:35,130 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-02-14 22:22:35,130 INFO L506 BasicCegarLoop]: Found error trace [2022-02-14 22:22:35,130 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-14 22:22:35,155 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-02-14 22:22:35,343 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:35,344 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-14 22:22:35,344 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-14 22:22:35,344 INFO L85 PathProgramCache]: Analyzing trace with hash 1651364104, now seen corresponding path program 1 times [2022-02-14 22:22:35,344 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-14 22:22:35,344 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [371061720] [2022-02-14 22:22:35,344 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:35,345 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-14 22:22:35,359 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-14 22:22:35,359 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1824169518] [2022-02-14 22:22:35,359 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:35,359 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:35,359 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-14 22:22:35,365 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-02-14 22:22:35,383 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-02-14 22:22:35,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-14 22:22:35,411 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 11 conjunts are in the unsatisfiable core [2022-02-14 22:22:35,413 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-14 22:22:35,489 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-02-14 22:22:35,489 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-14 22:22:35,588 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-02-14 22:22:35,588 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-14 22:22:35,588 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [371061720] [2022-02-14 22:22:35,589 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-14 22:22:35,589 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1824169518] [2022-02-14 22:22:35,589 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1824169518] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-14 22:22:35,589 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-14 22:22:35,589 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 9 [2022-02-14 22:22:35,589 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1183660472] [2022-02-14 22:22:35,589 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-14 22:22:35,590 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-02-14 22:22:35,590 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-14 22:22:35,590 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-02-14 22:22:35,590 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2022-02-14 22:22:35,590 INFO L87 Difference]: Start difference. First operand 93 states and 112 transitions. Second operand has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-02-14 22:22:35,678 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-14 22:22:35,680 INFO L93 Difference]: Finished difference Result 106 states and 121 transitions. [2022-02-14 22:22:35,683 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-02-14 22:22:35,683 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2022-02-14 22:22:35,683 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-14 22:22:35,684 INFO L225 Difference]: With dead ends: 106 [2022-02-14 22:22:35,684 INFO L226 Difference]: Without dead ends: 88 [2022-02-14 22:22:35,685 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2022-02-14 22:22:35,685 INFO L933 BasicCegarLoop]: 21 mSDtfsCounter, 17 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 92 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.1s IncrementalHoareTripleChecker+Time [2022-02-14 22:22:35,686 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 92 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-14 22:22:35,686 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2022-02-14 22:22:35,688 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 88. [2022-02-14 22:22:35,689 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 69 states have (on average 1.2318840579710144) internal successors, (85), 73 states have internal predecessors, (85), 10 states have call successors, (10), 9 states have call predecessors, (10), 8 states have return successors, (8), 5 states have call predecessors, (8), 8 states have call successors, (8) [2022-02-14 22:22:35,689 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 103 transitions. [2022-02-14 22:22:35,689 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 103 transitions. Word has length 24 [2022-02-14 22:22:35,690 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-14 22:22:35,690 INFO L470 AbstractCegarLoop]: Abstraction has 88 states and 103 transitions. [2022-02-14 22:22:35,690 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-02-14 22:22:35,690 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 103 transitions. [2022-02-14 22:22:35,691 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-02-14 22:22:35,691 INFO L506 BasicCegarLoop]: Found error trace [2022-02-14 22:22:35,691 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-14 22:22:35,715 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-02-14 22:22:35,891 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:35,892 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-14 22:22:35,892 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-14 22:22:35,892 INFO L85 PathProgramCache]: Analyzing trace with hash -268589446, now seen corresponding path program 1 times [2022-02-14 22:22:35,893 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-14 22:22:35,893 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1751694536] [2022-02-14 22:22:35,893 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:35,893 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-14 22:22:35,903 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-14 22:22:35,903 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [569149921] [2022-02-14 22:22:35,903 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:22:35,903 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:22:35,903 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-14 22:22:35,904 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-02-14 22:22:35,908 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-02-14 22:22:35,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-14 22:22:35,974 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 25 conjunts are in the unsatisfiable core [2022-02-14 22:22:35,975 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-14 22:22:36,273 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-02-14 22:22:36,274 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-14 22:23:08,374 WARN L860 $PredicateComparison]: unable to prove that (let ((.cse1 (mod (* c_main_~b~0 2) 4294967296)) (.cse0 (mod c_main_~r~0 4294967296))) (or (not (<= (mod c_main_~b~0 4294967296) .cse0)) (= (mod c_main_~A~0 4294967296) (mod (+ (* (div .cse1 2) (* c_main_~q~0 2)) c_main_~r~0) 4294967296)) (<= .cse1 .cse0))) is different from true [2022-02-14 22:23:17,945 WARN L228 SmtUtils]: Spent 5.29s on a formula simplification that was a NOOP. DAG size: 7 (called from [L1067] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2022-02-14 22:23:28,649 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 3 not checked. [2022-02-14 22:23:28,650 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-14 22:23:28,650 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1751694536] [2022-02-14 22:23:28,650 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-14 22:23:28,650 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [569149921] [2022-02-14 22:23:28,650 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [569149921] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-14 22:23:28,650 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-14 22:23:28,650 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 13 [2022-02-14 22:23:28,651 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1446096387] [2022-02-14 22:23:28,651 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-14 22:23:28,651 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-02-14 22:23:28,651 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-14 22:23:28,651 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-02-14 22:23:28,652 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=95, Unknown=2, NotChecked=20, Total=156 [2022-02-14 22:23:28,652 INFO L87 Difference]: Start difference. First operand 88 states and 103 transitions. Second operand has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 12 states have internal predecessors, (34), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-02-14 22:23:39,276 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-14 22:23:41,388 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.11s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-14 22:23:43,503 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.11s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-14 22:23:45,623 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-14 22:23:47,773 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.15s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-14 22:23:49,914 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-02-14 22:23:52,046 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-02-14 22:23:54,164 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-14 22:23:56,282 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-14 22:23:58,424 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.14s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-14 22:24:00,582 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-02-14 22:24:02,751 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-02-14 22:24:04,893 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.14s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-14 22:24:07,043 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.15s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-14 22:24:09,208 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-02-14 22:24:11,381 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-14 22:24:13,710 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-02-14 22:24:13,710 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-14 22:24:13,710 INFO L93 Difference]: Finished difference Result 98 states and 112 transitions. [2022-02-14 22:24:13,823 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-02-14 22:24:13,824 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 12 states have internal predecessors, (34), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 27 [2022-02-14 22:24:13,824 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-14 22:24:13,825 INFO L225 Difference]: With dead ends: 98 [2022-02-14 22:24:13,825 INFO L226 Difference]: Without dead ends: 98 [2022-02-14 22:24:13,825 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 40 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 13.0s TimeCoverageRelationStatistics Valid=52, Invalid=130, Unknown=4, NotChecked=24, Total=210 [2022-02-14 22:24:13,825 INFO L933 BasicCegarLoop]: 24 mSDtfsCounter, 22 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 70 mSolverCounterSat, 8 mSolverCounterUnsat, 17 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 34.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 162 SdHoareTripleChecker+Invalid, 138 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 70 IncrementalHoareTripleChecker+Invalid, 17 IncrementalHoareTripleChecker+Unknown, 43 IncrementalHoareTripleChecker+Unchecked, 36.4s IncrementalHoareTripleChecker+Time [2022-02-14 22:24:13,826 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 162 Invalid, 138 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 70 Invalid, 17 Unknown, 43 Unchecked, 36.4s Time] [2022-02-14 22:24:13,826 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2022-02-14 22:24:13,828 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 90. [2022-02-14 22:24:13,829 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 71 states have (on average 1.2112676056338028) internal successors, (86), 74 states have internal predecessors, (86), 10 states have call successors, (10), 9 states have call predecessors, (10), 8 states have return successors, (8), 6 states have call predecessors, (8), 8 states have call successors, (8) [2022-02-14 22:24:13,829 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 104 transitions. [2022-02-14 22:24:13,829 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 104 transitions. Word has length 27 [2022-02-14 22:24:13,829 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-14 22:24:13,830 INFO L470 AbstractCegarLoop]: Abstraction has 90 states and 104 transitions. [2022-02-14 22:24:13,830 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 12 states have internal predecessors, (34), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-02-14 22:24:13,830 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 104 transitions. [2022-02-14 22:24:13,831 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-02-14 22:24:13,831 INFO L506 BasicCegarLoop]: Found error trace [2022-02-14 22:24:13,831 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-14 22:24:13,853 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2022-02-14 22:24:14,047 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-02-14 22:24:14,048 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-14 22:24:14,048 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-14 22:24:14,048 INFO L85 PathProgramCache]: Analyzing trace with hash -142927336, now seen corresponding path program 1 times [2022-02-14 22:24:14,048 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-14 22:24:14,048 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1099153690] [2022-02-14 22:24:14,049 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:24:14,049 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-14 22:24:14,065 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-14 22:24:14,065 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [189420815] [2022-02-14 22:24:14,065 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-14 22:24:14,065 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-14 22:24:14,065 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-14 22:24:14,075 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-02-14 22:24:14,076 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process