./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/verifythis/prefixsum_rec.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version f4d5612c Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx12G -Xms1G -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/verifythis/prefixsum_rec.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(__VERIFIER_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 4f7077bba653370b680c2ff46ec9417a9e7cf514 ........................................................................................................................................................................................................................................................................................... Execution finished normally Using bit-precise analysis Retrying with bit-precise analysis Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx12G -Xms1G -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/verifythis/prefixsum_rec.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(__VERIFIER_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 4f7077bba653370b680c2ff46ec9417a9e7cf514 ..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... Execution finished normally Writing output log to file Ultimate.log Result: ERROR: ExceptionOrErrorResult: AssertionError: Alternating quantifiers not yet supported --- Real Ultimate output --- This is Ultimate 0.1.24-f4d5612 [2019-11-28 12:30:14,226 INFO L177 SettingsManager]: Resetting all preferences to default values... [2019-11-28 12:30:14,231 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2019-11-28 12:30:14,244 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2019-11-28 12:30:14,244 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2019-11-28 12:30:14,245 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2019-11-28 12:30:14,247 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2019-11-28 12:30:14,249 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2019-11-28 12:30:14,251 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2019-11-28 12:30:14,252 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2019-11-28 12:30:14,253 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2019-11-28 12:30:14,254 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2019-11-28 12:30:14,255 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2019-11-28 12:30:14,256 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2019-11-28 12:30:14,257 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2019-11-28 12:30:14,258 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2019-11-28 12:30:14,259 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2019-11-28 12:30:14,260 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2019-11-28 12:30:14,262 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2019-11-28 12:30:14,264 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2019-11-28 12:30:14,266 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2019-11-28 12:30:14,267 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2019-11-28 12:30:14,268 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2019-11-28 12:30:14,269 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2019-11-28 12:30:14,272 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2019-11-28 12:30:14,272 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2019-11-28 12:30:14,272 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2019-11-28 12:30:14,273 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2019-11-28 12:30:14,274 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2019-11-28 12:30:14,275 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2019-11-28 12:30:14,275 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2019-11-28 12:30:14,276 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2019-11-28 12:30:14,277 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2019-11-28 12:30:14,278 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2019-11-28 12:30:14,279 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2019-11-28 12:30:14,279 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2019-11-28 12:30:14,280 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2019-11-28 12:30:14,280 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2019-11-28 12:30:14,281 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2019-11-28 12:30:14,282 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2019-11-28 12:30:14,283 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2019-11-28 12:30:14,284 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2019-11-28 12:30:14,298 INFO L113 SettingsManager]: Loading preferences was successful [2019-11-28 12:30:14,299 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2019-11-28 12:30:14,300 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2019-11-28 12:30:14,300 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2019-11-28 12:30:14,301 INFO L138 SettingsManager]: * Use SBE=true [2019-11-28 12:30:14,301 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2019-11-28 12:30:14,301 INFO L138 SettingsManager]: * sizeof long=4 [2019-11-28 12:30:14,302 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2019-11-28 12:30:14,302 INFO L138 SettingsManager]: * sizeof POINTER=4 [2019-11-28 12:30:14,302 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2019-11-28 12:30:14,302 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2019-11-28 12:30:14,303 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2019-11-28 12:30:14,303 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2019-11-28 12:30:14,303 INFO L138 SettingsManager]: * sizeof long double=12 [2019-11-28 12:30:14,304 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2019-11-28 12:30:14,304 INFO L138 SettingsManager]: * Use constant arrays=true [2019-11-28 12:30:14,304 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2019-11-28 12:30:14,304 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2019-11-28 12:30:14,305 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2019-11-28 12:30:14,305 INFO L138 SettingsManager]: * To the following directory=./dump/ [2019-11-28 12:30:14,305 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2019-11-28 12:30:14,306 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2019-11-28 12:30:14,306 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2019-11-28 12:30:14,306 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2019-11-28 12:30:14,306 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2019-11-28 12:30:14,307 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2019-11-28 12:30:14,307 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2019-11-28 12:30:14,307 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2019-11-28 12:30:14,307 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(__VERIFIER_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 4f7077bba653370b680c2ff46ec9417a9e7cf514 [2019-11-28 12:30:14,625 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2019-11-28 12:30:14,639 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2019-11-28 12:30:14,644 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2019-11-28 12:30:14,645 INFO L271 PluginConnector]: Initializing CDTParser... [2019-11-28 12:30:14,646 INFO L275 PluginConnector]: CDTParser initialized [2019-11-28 12:30:14,647 INFO L428 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/verifythis/prefixsum_rec.c [2019-11-28 12:30:14,722 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/20a556cc3/81ee329d718f48daa16944137050aa83/FLAG924613480 [2019-11-28 12:30:15,184 INFO L306 CDTParser]: Found 1 translation units. [2019-11-28 12:30:15,184 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/verifythis/prefixsum_rec.c [2019-11-28 12:30:15,192 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/20a556cc3/81ee329d718f48daa16944137050aa83/FLAG924613480 [2019-11-28 12:30:15,563 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/20a556cc3/81ee329d718f48daa16944137050aa83 [2019-11-28 12:30:15,566 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2019-11-28 12:30:15,568 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2019-11-28 12:30:15,569 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2019-11-28 12:30:15,569 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2019-11-28 12:30:15,573 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2019-11-28 12:30:15,574 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.11 12:30:15" (1/1) ... [2019-11-28 12:30:15,576 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1b88ebbd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:15, skipping insertion in model container [2019-11-28 12:30:15,577 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.11 12:30:15" (1/1) ... [2019-11-28 12:30:15,585 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2019-11-28 12:30:15,604 INFO L178 MainTranslator]: Built tables and reachable declarations [2019-11-28 12:30:15,826 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-11-28 12:30:15,840 INFO L203 MainTranslator]: Completed pre-run [2019-11-28 12:30:15,868 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-11-28 12:30:15,941 INFO L208 MainTranslator]: Completed translation [2019-11-28 12:30:15,941 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:15 WrapperNode [2019-11-28 12:30:15,942 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2019-11-28 12:30:15,942 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2019-11-28 12:30:15,942 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2019-11-28 12:30:15,943 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2019-11-28 12:30:15,951 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:15" (1/1) ... [2019-11-28 12:30:15,962 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:15" (1/1) ... [2019-11-28 12:30:15,989 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2019-11-28 12:30:15,989 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2019-11-28 12:30:15,990 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2019-11-28 12:30:15,990 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2019-11-28 12:30:15,997 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:15" (1/1) ... [2019-11-28 12:30:15,997 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:15" (1/1) ... [2019-11-28 12:30:16,000 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:15" (1/1) ... [2019-11-28 12:30:16,001 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:15" (1/1) ... [2019-11-28 12:30:16,009 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:15" (1/1) ... [2019-11-28 12:30:16,014 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:15" (1/1) ... [2019-11-28 12:30:16,017 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:15" (1/1) ... [2019-11-28 12:30:16,020 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2019-11-28 12:30:16,020 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2019-11-28 12:30:16,020 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2019-11-28 12:30:16,021 INFO L275 PluginConnector]: RCFGBuilder initialized [2019-11-28 12:30:16,021 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:15" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2019-11-28 12:30:16,077 INFO L130 BoogieDeclarations]: Found specification of procedure downsweep [2019-11-28 12:30:16,078 INFO L138 BoogieDeclarations]: Found implementation of procedure downsweep [2019-11-28 12:30:16,078 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2019-11-28 12:30:16,078 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2019-11-28 12:30:16,079 INFO L130 BoogieDeclarations]: Found specification of procedure upsweep [2019-11-28 12:30:16,079 INFO L138 BoogieDeclarations]: Found implementation of procedure upsweep [2019-11-28 12:30:16,079 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2019-11-28 12:30:16,079 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2019-11-28 12:30:16,079 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2019-11-28 12:30:16,080 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2019-11-28 12:30:16,465 INFO L282 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2019-11-28 12:30:16,465 INFO L287 CfgBuilder]: Removed 17 assume(true) statements. [2019-11-28 12:30:16,466 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.11 12:30:16 BoogieIcfgContainer [2019-11-28 12:30:16,467 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2019-11-28 12:30:16,468 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2019-11-28 12:30:16,468 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2019-11-28 12:30:16,471 INFO L275 PluginConnector]: TraceAbstraction initialized [2019-11-28 12:30:16,471 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 28.11 12:30:15" (1/3) ... [2019-11-28 12:30:16,472 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@45314719 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.11 12:30:16, skipping insertion in model container [2019-11-28 12:30:16,472 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:15" (2/3) ... [2019-11-28 12:30:16,473 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@45314719 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.11 12:30:16, skipping insertion in model container [2019-11-28 12:30:16,473 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.11 12:30:16" (3/3) ... [2019-11-28 12:30:16,474 INFO L109 eAbstractionObserver]: Analyzing ICFG prefixsum_rec.c [2019-11-28 12:30:16,482 INFO L156 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2019-11-28 12:30:16,490 INFO L168 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2019-11-28 12:30:16,502 INFO L249 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2019-11-28 12:30:16,526 INFO L373 AbstractCegarLoop]: Interprodecural is true [2019-11-28 12:30:16,526 INFO L374 AbstractCegarLoop]: Hoare is true [2019-11-28 12:30:16,527 INFO L375 AbstractCegarLoop]: Compute interpolants for FPandBP [2019-11-28 12:30:16,527 INFO L376 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2019-11-28 12:30:16,527 INFO L377 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2019-11-28 12:30:16,527 INFO L378 AbstractCegarLoop]: Difference is false [2019-11-28 12:30:16,527 INFO L379 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2019-11-28 12:30:16,527 INFO L383 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2019-11-28 12:30:16,544 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states. [2019-11-28 12:30:16,550 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2019-11-28 12:30:16,551 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:30:16,551 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:30:16,552 INFO L410 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:30:16,558 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:30:16,558 INFO L82 PathProgramCache]: Analyzing trace with hash -1360829009, now seen corresponding path program 1 times [2019-11-28 12:30:16,565 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-28 12:30:16,566 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1553648854] [2019-11-28 12:30:16,566 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-28 12:30:16,707 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-28 12:30:16,836 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-28 12:30:16,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-28 12:30:16,881 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-28 12:30:16,885 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1553648854] [2019-11-28 12:30:16,885 INFO L220 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2019-11-28 12:30:16,887 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2019-11-28 12:30:16,888 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [731680635] [2019-11-28 12:30:16,893 INFO L442 AbstractCegarLoop]: Interpolant automaton has 5 states [2019-11-28 12:30:16,893 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2019-11-28 12:30:16,903 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2019-11-28 12:30:16,904 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2019-11-28 12:30:16,906 INFO L87 Difference]: Start difference. First operand 36 states. Second operand 5 states. [2019-11-28 12:30:17,072 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-28 12:30:17,072 INFO L93 Difference]: Finished difference Result 72 states and 96 transitions. [2019-11-28 12:30:17,073 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2019-11-28 12:30:17,074 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 24 [2019-11-28 12:30:17,075 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-28 12:30:17,084 INFO L225 Difference]: With dead ends: 72 [2019-11-28 12:30:17,084 INFO L226 Difference]: Without dead ends: 35 [2019-11-28 12:30:17,089 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2019-11-28 12:30:17,106 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2019-11-28 12:30:17,127 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 33. [2019-11-28 12:30:17,128 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 33 states. [2019-11-28 12:30:17,130 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 41 transitions. [2019-11-28 12:30:17,132 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 41 transitions. Word has length 24 [2019-11-28 12:30:17,132 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-28 12:30:17,133 INFO L462 AbstractCegarLoop]: Abstraction has 33 states and 41 transitions. [2019-11-28 12:30:17,133 INFO L463 AbstractCegarLoop]: Interpolant automaton has 5 states. [2019-11-28 12:30:17,133 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 41 transitions. [2019-11-28 12:30:17,135 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2019-11-28 12:30:17,136 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:30:17,136 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:30:17,136 INFO L410 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:30:17,137 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:30:17,137 INFO L82 PathProgramCache]: Analyzing trace with hash -1965744595, now seen corresponding path program 1 times [2019-11-28 12:30:17,137 INFO L163 FreeRefinementEngine]: Executing refinement strategy CAMEL [2019-11-28 12:30:17,137 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [343112723] [2019-11-28 12:30:17,138 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2019-11-28 12:30:17,197 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-28 12:30:17,464 FATAL L? ?]: An unrecoverable error occured during an interaction with an SMT solver: de.uni_freiburg.informatik.ultimate.logic.SMTLIBException: Undeclared function symbol (const Int) at de.uni_freiburg.informatik.ultimate.logic.NoopScript.term(NoopScript.java:478) at de.uni_freiburg.informatik.ultimate.logic.WrapperScript.term(WrapperScript.java:250) at de.uni_freiburg.informatik.ultimate.logic.WrapperScript.term(WrapperScript.java:250) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.SmtUtils.termWithLocalSimplification(SmtUtils.java:1315) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.SmtUtils.termWithLocalSimplification(SmtUtils.java:1196) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.scripttransfer.TermTransferrer.convertApplicationTerm(TermTransferrer.java:182) at de.uni_freiburg.informatik.ultimate.logic.TermTransformer$BuildApplicationTerm.walk(TermTransformer.java:339) at de.uni_freiburg.informatik.ultimate.logic.NonRecursive.run(NonRecursive.java:115) at de.uni_freiburg.informatik.ultimate.logic.NonRecursive.run(NonRecursive.java:106) at de.uni_freiburg.informatik.ultimate.logic.TermTransformer.transform(TermTransformer.java:272) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.NestedInterpolantsBuilder.computePredicates(NestedInterpolantsBuilder.java:573) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.NestedInterpolantsBuilder.(NestedInterpolantsBuilder.java:171) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.InterpolatingTraceCheckCraig.computeInterpolantsRecursive(InterpolatingTraceCheckCraig.java:300) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.InterpolatingTraceCheckCraig.computeInterpolants(InterpolatingTraceCheckCraig.java:202) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.InterpolatingTraceCheckCraig.(InterpolatingTraceCheckCraig.java:107) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleCraig.construct(IpTcStrategyModuleCraig.java:79) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleCraig.construct(IpTcStrategyModuleCraig.java:1) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.isCorrect(IpTcStrategyModuleBase.java:57) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.checkFeasibility(AutomatonFreeRefinementEngine.java:242) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:166) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:75) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:463) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterateInternal(AbstractCegarLoop.java:419) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:368) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.CegarLoopResult.iterate(CegarLoopResult.java:139) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.iterateNew(TraceAbstractionStarter.java:332) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:174) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:126) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:120) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:316) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:55) [2019-11-28 12:30:17,472 INFO L168 Benchmark]: Toolchain (without parser) took 1902.03 ms. Allocated memory was 1.0 GB in the beginning and 1.2 GB in the end (delta: 132.1 MB). Free memory was 959.0 MB in the beginning and 1.0 GB in the end (delta: -76.3 MB). Peak memory consumption was 55.8 MB. Max. memory is 11.5 GB. [2019-11-28 12:30:17,473 INFO L168 Benchmark]: CDTParser took 0.60 ms. Allocated memory is still 1.0 GB. Free memory is still 987.2 MB. There was no memory consumed. Max. memory is 11.5 GB. [2019-11-28 12:30:17,475 INFO L168 Benchmark]: CACSL2BoogieTranslator took 373.15 ms. Allocated memory was 1.0 GB in the beginning and 1.2 GB in the end (delta: 132.1 MB). Free memory was 959.0 MB in the beginning and 1.1 GB in the end (delta: -169.5 MB). Peak memory consumption was 20.6 MB. Max. memory is 11.5 GB. [2019-11-28 12:30:17,477 INFO L168 Benchmark]: Boogie Procedure Inliner took 46.92 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 6.6 MB). Peak memory consumption was 6.6 MB. Max. memory is 11.5 GB. [2019-11-28 12:30:17,477 INFO L168 Benchmark]: Boogie Preprocessor took 30.42 ms. Allocated memory is still 1.2 GB. Free memory is still 1.1 GB. There was no memory consumed. Max. memory is 11.5 GB. [2019-11-28 12:30:17,479 INFO L168 Benchmark]: RCFGBuilder took 446.51 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 26.9 MB). Peak memory consumption was 26.9 MB. Max. memory is 11.5 GB. [2019-11-28 12:30:17,480 INFO L168 Benchmark]: TraceAbstraction took 1000.23 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.0 GB in the end (delta: 59.7 MB). Peak memory consumption was 59.7 MB. Max. memory is 11.5 GB. [2019-11-28 12:30:17,490 INFO L335 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.60 ms. Allocated memory is still 1.0 GB. Free memory is still 987.2 MB. There was no memory consumed. Max. memory is 11.5 GB. * CACSL2BoogieTranslator took 373.15 ms. Allocated memory was 1.0 GB in the beginning and 1.2 GB in the end (delta: 132.1 MB). Free memory was 959.0 MB in the beginning and 1.1 GB in the end (delta: -169.5 MB). Peak memory consumption was 20.6 MB. Max. memory is 11.5 GB. * Boogie Procedure Inliner took 46.92 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 6.6 MB). Peak memory consumption was 6.6 MB. Max. memory is 11.5 GB. * Boogie Preprocessor took 30.42 ms. Allocated memory is still 1.2 GB. Free memory is still 1.1 GB. There was no memory consumed. Max. memory is 11.5 GB. * RCFGBuilder took 446.51 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 26.9 MB). Peak memory consumption was 26.9 MB. Max. memory is 11.5 GB. * TraceAbstraction took 1000.23 ms. Allocated memory is still 1.2 GB. Free memory was 1.1 GB in the beginning and 1.0 GB in the end (delta: 59.7 MB). Peak memory consumption was 59.7 MB. Max. memory is 11.5 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - ExceptionOrErrorResult: SMTLIBException: Undeclared function symbol (const Int) de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: SMTLIBException: Undeclared function symbol (const Int): de.uni_freiburg.informatik.ultimate.logic.NoopScript.term(NoopScript.java:478) RESULT: Ultimate could not prove your program: Toolchain returned no result. Received shutdown request... ### Bit-precise run ### This is Ultimate 0.1.24-f4d5612 [2019-11-28 12:30:19,485 INFO L177 SettingsManager]: Resetting all preferences to default values... [2019-11-28 12:30:19,490 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2019-11-28 12:30:19,506 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2019-11-28 12:30:19,506 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2019-11-28 12:30:19,508 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2019-11-28 12:30:19,510 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2019-11-28 12:30:19,520 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2019-11-28 12:30:19,524 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2019-11-28 12:30:19,526 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2019-11-28 12:30:19,527 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2019-11-28 12:30:19,529 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2019-11-28 12:30:19,530 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2019-11-28 12:30:19,535 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2019-11-28 12:30:19,536 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2019-11-28 12:30:19,538 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2019-11-28 12:30:19,539 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2019-11-28 12:30:19,541 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2019-11-28 12:30:19,544 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2019-11-28 12:30:19,548 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2019-11-28 12:30:19,552 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2019-11-28 12:30:19,556 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2019-11-28 12:30:19,557 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2019-11-28 12:30:19,559 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2019-11-28 12:30:19,561 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2019-11-28 12:30:19,562 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2019-11-28 12:30:19,562 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2019-11-28 12:30:19,563 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2019-11-28 12:30:19,564 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2019-11-28 12:30:19,565 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2019-11-28 12:30:19,565 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2019-11-28 12:30:19,566 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2019-11-28 12:30:19,566 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2019-11-28 12:30:19,568 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2019-11-28 12:30:19,569 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2019-11-28 12:30:19,569 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2019-11-28 12:30:19,570 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2019-11-28 12:30:19,570 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2019-11-28 12:30:19,570 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2019-11-28 12:30:19,571 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2019-11-28 12:30:19,573 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2019-11-28 12:30:19,573 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.epf [2019-11-28 12:30:19,607 INFO L113 SettingsManager]: Loading preferences was successful [2019-11-28 12:30:19,608 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2019-11-28 12:30:19,609 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2019-11-28 12:30:19,614 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2019-11-28 12:30:19,614 INFO L138 SettingsManager]: * Use SBE=true [2019-11-28 12:30:19,614 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2019-11-28 12:30:19,615 INFO L138 SettingsManager]: * sizeof long=4 [2019-11-28 12:30:19,615 INFO L138 SettingsManager]: * sizeof POINTER=4 [2019-11-28 12:30:19,615 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2019-11-28 12:30:19,615 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2019-11-28 12:30:19,616 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2019-11-28 12:30:19,616 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2019-11-28 12:30:19,616 INFO L138 SettingsManager]: * Use bitvectors instead of ints=true [2019-11-28 12:30:19,616 INFO L138 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2019-11-28 12:30:19,616 INFO L138 SettingsManager]: * sizeof long double=12 [2019-11-28 12:30:19,617 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2019-11-28 12:30:19,617 INFO L138 SettingsManager]: * Use constant arrays=true [2019-11-28 12:30:19,617 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2019-11-28 12:30:19,617 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2019-11-28 12:30:19,618 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2019-11-28 12:30:19,618 INFO L138 SettingsManager]: * To the following directory=./dump/ [2019-11-28 12:30:19,618 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2019-11-28 12:30:19,618 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2019-11-28 12:30:19,619 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2019-11-28 12:30:19,619 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2019-11-28 12:30:19,619 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2019-11-28 12:30:19,619 INFO L138 SettingsManager]: * Trace refinement strategy=WOLF [2019-11-28 12:30:19,619 INFO L138 SettingsManager]: * Command for external solver=cvc4 --incremental --rewrite-divk --print-success --lang smt [2019-11-28 12:30:19,620 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2019-11-28 12:30:19,620 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2019-11-28 12:30:19,620 INFO L138 SettingsManager]: * Logic for external solver=AUFBV Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(__VERIFIER_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 4f7077bba653370b680c2ff46ec9417a9e7cf514 [2019-11-28 12:30:19,940 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2019-11-28 12:30:19,956 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2019-11-28 12:30:19,959 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2019-11-28 12:30:19,961 INFO L271 PluginConnector]: Initializing CDTParser... [2019-11-28 12:30:19,962 INFO L275 PluginConnector]: CDTParser initialized [2019-11-28 12:30:19,963 INFO L428 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/verifythis/prefixsum_rec.c [2019-11-28 12:30:20,041 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ddb9cf55d/3759b8183313422692294710f2328822/FLAGe5a862d20 [2019-11-28 12:30:20,520 INFO L306 CDTParser]: Found 1 translation units. [2019-11-28 12:30:20,521 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/verifythis/prefixsum_rec.c [2019-11-28 12:30:20,528 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ddb9cf55d/3759b8183313422692294710f2328822/FLAGe5a862d20 [2019-11-28 12:30:20,906 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ddb9cf55d/3759b8183313422692294710f2328822 [2019-11-28 12:30:20,912 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2019-11-28 12:30:20,914 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2019-11-28 12:30:20,916 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2019-11-28 12:30:20,916 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2019-11-28 12:30:20,920 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2019-11-28 12:30:20,921 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.11 12:30:20" (1/1) ... [2019-11-28 12:30:20,924 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7d8d6d23 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:20, skipping insertion in model container [2019-11-28 12:30:20,924 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.11 12:30:20" (1/1) ... [2019-11-28 12:30:20,935 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2019-11-28 12:30:20,961 INFO L178 MainTranslator]: Built tables and reachable declarations [2019-11-28 12:30:21,216 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-11-28 12:30:21,230 INFO L203 MainTranslator]: Completed pre-run [2019-11-28 12:30:21,323 INFO L206 PostProcessor]: Analyzing one entry point: main [2019-11-28 12:30:21,342 INFO L208 MainTranslator]: Completed translation [2019-11-28 12:30:21,342 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:21 WrapperNode [2019-11-28 12:30:21,342 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2019-11-28 12:30:21,343 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2019-11-28 12:30:21,343 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2019-11-28 12:30:21,343 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2019-11-28 12:30:21,353 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:21" (1/1) ... [2019-11-28 12:30:21,365 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:21" (1/1) ... [2019-11-28 12:30:21,390 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2019-11-28 12:30:21,391 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2019-11-28 12:30:21,391 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2019-11-28 12:30:21,391 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2019-11-28 12:30:21,399 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:21" (1/1) ... [2019-11-28 12:30:21,399 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:21" (1/1) ... [2019-11-28 12:30:21,404 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:21" (1/1) ... [2019-11-28 12:30:21,404 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:21" (1/1) ... [2019-11-28 12:30:21,413 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:21" (1/1) ... [2019-11-28 12:30:21,419 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:21" (1/1) ... [2019-11-28 12:30:21,421 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:21" (1/1) ... [2019-11-28 12:30:21,425 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2019-11-28 12:30:21,426 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2019-11-28 12:30:21,426 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2019-11-28 12:30:21,426 INFO L275 PluginConnector]: RCFGBuilder initialized [2019-11-28 12:30:21,427 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:21" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2019-11-28 12:30:21,481 INFO L130 BoogieDeclarations]: Found specification of procedure downsweep [2019-11-28 12:30:21,481 INFO L138 BoogieDeclarations]: Found implementation of procedure downsweep [2019-11-28 12:30:21,482 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2019-11-28 12:30:21,482 INFO L130 BoogieDeclarations]: Found specification of procedure read~intINTTYPE4 [2019-11-28 12:30:21,482 INFO L130 BoogieDeclarations]: Found specification of procedure upsweep [2019-11-28 12:30:21,482 INFO L138 BoogieDeclarations]: Found implementation of procedure upsweep [2019-11-28 12:30:21,482 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2019-11-28 12:30:21,482 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2019-11-28 12:30:21,482 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2019-11-28 12:30:21,483 INFO L130 BoogieDeclarations]: Found specification of procedure write~intINTTYPE4 [2019-11-28 12:30:21,899 INFO L282 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2019-11-28 12:30:21,900 INFO L287 CfgBuilder]: Removed 17 assume(true) statements. [2019-11-28 12:30:21,901 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.11 12:30:21 BoogieIcfgContainer [2019-11-28 12:30:21,901 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2019-11-28 12:30:21,902 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2019-11-28 12:30:21,902 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2019-11-28 12:30:21,907 INFO L275 PluginConnector]: TraceAbstraction initialized [2019-11-28 12:30:21,908 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 28.11 12:30:20" (1/3) ... [2019-11-28 12:30:21,909 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5ede0f9a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.11 12:30:21, skipping insertion in model container [2019-11-28 12:30:21,909 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 12:30:21" (2/3) ... [2019-11-28 12:30:21,910 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5ede0f9a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.11 12:30:21, skipping insertion in model container [2019-11-28 12:30:21,911 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.11 12:30:21" (3/3) ... [2019-11-28 12:30:21,913 INFO L109 eAbstractionObserver]: Analyzing ICFG prefixsum_rec.c [2019-11-28 12:30:21,922 INFO L156 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2019-11-28 12:30:21,929 INFO L168 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2019-11-28 12:30:21,938 INFO L249 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2019-11-28 12:30:21,959 INFO L373 AbstractCegarLoop]: Interprodecural is true [2019-11-28 12:30:21,959 INFO L374 AbstractCegarLoop]: Hoare is true [2019-11-28 12:30:21,959 INFO L375 AbstractCegarLoop]: Compute interpolants for FPandBP [2019-11-28 12:30:21,959 INFO L376 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2019-11-28 12:30:21,960 INFO L377 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2019-11-28 12:30:21,960 INFO L378 AbstractCegarLoop]: Difference is false [2019-11-28 12:30:21,960 INFO L379 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2019-11-28 12:30:21,960 INFO L383 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2019-11-28 12:30:21,978 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states. [2019-11-28 12:30:21,985 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2019-11-28 12:30:21,985 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:30:21,986 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:30:21,987 INFO L410 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:30:21,991 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:30:21,992 INFO L82 PathProgramCache]: Analyzing trace with hash -1360829009, now seen corresponding path program 1 times [2019-11-28 12:30:22,002 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-28 12:30:22,003 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [813881343] [2019-11-28 12:30:22,003 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 2 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with mathsat -unsat_core_generation=3 [2019-11-28 12:30:22,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-28 12:30:22,117 INFO L255 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 5 conjunts are in the unsatisfiable core [2019-11-28 12:30:22,124 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-28 12:30:22,165 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:30:22,193 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-28 12:30:22,194 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-28 12:30:22,249 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-28 12:30:22,251 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [813881343] [2019-11-28 12:30:22,252 INFO L220 FreeRefinementEngine]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2019-11-28 12:30:22,252 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4, 4] imperfect sequences [] total 5 [2019-11-28 12:30:22,253 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [232657465] [2019-11-28 12:30:22,259 INFO L442 AbstractCegarLoop]: Interpolant automaton has 5 states [2019-11-28 12:30:22,260 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-28 12:30:22,274 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2019-11-28 12:30:22,275 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2019-11-28 12:30:22,277 INFO L87 Difference]: Start difference. First operand 36 states. Second operand 5 states. [2019-11-28 12:30:22,366 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-28 12:30:22,367 INFO L93 Difference]: Finished difference Result 72 states and 96 transitions. [2019-11-28 12:30:22,368 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2019-11-28 12:30:22,369 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 24 [2019-11-28 12:30:22,370 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-28 12:30:22,379 INFO L225 Difference]: With dead ends: 72 [2019-11-28 12:30:22,379 INFO L226 Difference]: Without dead ends: 33 [2019-11-28 12:30:22,384 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2019-11-28 12:30:22,404 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2019-11-28 12:30:22,455 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2019-11-28 12:30:22,458 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 33 states. [2019-11-28 12:30:22,461 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 41 transitions. [2019-11-28 12:30:22,463 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 41 transitions. Word has length 24 [2019-11-28 12:30:22,465 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-28 12:30:22,465 INFO L462 AbstractCegarLoop]: Abstraction has 33 states and 41 transitions. [2019-11-28 12:30:22,465 INFO L463 AbstractCegarLoop]: Interpolant automaton has 5 states. [2019-11-28 12:30:22,466 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 41 transitions. [2019-11-28 12:30:22,469 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2019-11-28 12:30:22,470 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:30:22,470 INFO L410 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:30:22,682 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 mathsat -unsat_core_generation=3 [2019-11-28 12:30:22,683 INFO L410 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:30:22,683 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:30:22,683 INFO L82 PathProgramCache]: Analyzing trace with hash 1851866079, now seen corresponding path program 1 times [2019-11-28 12:30:22,684 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-28 12:30:22,685 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [2074763490] [2019-11-28 12:30:22,685 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 3 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with mathsat -unsat_core_generation=3 [2019-11-28 12:30:22,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-28 12:30:22,776 INFO L255 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 8 conjunts are in the unsatisfiable core [2019-11-28 12:30:22,779 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-28 12:30:22,862 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:30:22,923 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-28 12:30:22,923 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-28 12:30:23,083 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-28 12:30:23,083 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [2074763490] [2019-11-28 12:30:23,084 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-28 12:30:23,084 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2019-11-28 12:30:23,084 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1551099785] [2019-11-28 12:30:23,089 INFO L442 AbstractCegarLoop]: Interpolant automaton has 12 states [2019-11-28 12:30:23,089 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-28 12:30:23,091 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2019-11-28 12:30:23,091 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2019-11-28 12:30:23,091 INFO L87 Difference]: Start difference. First operand 33 states and 41 transitions. Second operand 12 states. [2019-11-28 12:30:23,631 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-28 12:30:23,632 INFO L93 Difference]: Finished difference Result 77 states and 98 transitions. [2019-11-28 12:30:23,633 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2019-11-28 12:30:23,633 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 25 [2019-11-28 12:30:23,634 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-28 12:30:23,635 INFO L225 Difference]: With dead ends: 77 [2019-11-28 12:30:23,635 INFO L226 Difference]: Without dead ends: 54 [2019-11-28 12:30:23,640 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=100, Invalid=172, Unknown=0, NotChecked=0, Total=272 [2019-11-28 12:30:23,641 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2019-11-28 12:30:23,666 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 41. [2019-11-28 12:30:23,667 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2019-11-28 12:30:23,670 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 50 transitions. [2019-11-28 12:30:23,670 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 50 transitions. Word has length 25 [2019-11-28 12:30:23,672 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-28 12:30:23,672 INFO L462 AbstractCegarLoop]: Abstraction has 41 states and 50 transitions. [2019-11-28 12:30:23,674 INFO L463 AbstractCegarLoop]: Interpolant automaton has 12 states. [2019-11-28 12:30:23,674 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 50 transitions. [2019-11-28 12:30:23,675 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2019-11-28 12:30:23,676 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:30:23,677 INFO L410 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:30:23,896 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 mathsat -unsat_core_generation=3 [2019-11-28 12:30:23,896 INFO L410 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:30:23,896 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:30:23,897 INFO L82 PathProgramCache]: Analyzing trace with hash 1995858989, now seen corresponding path program 1 times [2019-11-28 12:30:23,897 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-28 12:30:23,897 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1231708524] [2019-11-28 12:30:23,898 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 4 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with mathsat -unsat_core_generation=3 [2019-11-28 12:30:23,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-28 12:30:23,991 INFO L255 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 10 conjunts are in the unsatisfiable core [2019-11-28 12:30:23,993 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-28 12:30:24,087 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:30:24,168 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-28 12:30:24,169 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-28 12:30:24,380 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-28 12:30:24,380 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1231708524] [2019-11-28 12:30:24,381 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-28 12:30:24,381 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2019-11-28 12:30:24,381 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [487432446] [2019-11-28 12:30:24,382 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2019-11-28 12:30:24,382 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-28 12:30:24,383 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2019-11-28 12:30:24,383 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=166, Unknown=0, NotChecked=0, Total=240 [2019-11-28 12:30:24,383 INFO L87 Difference]: Start difference. First operand 41 states and 50 transitions. Second operand 16 states. [2019-11-28 12:30:25,401 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-28 12:30:25,401 INFO L93 Difference]: Finished difference Result 103 states and 129 transitions. [2019-11-28 12:30:25,402 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2019-11-28 12:30:25,402 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 28 [2019-11-28 12:30:25,403 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-28 12:30:25,404 INFO L225 Difference]: With dead ends: 103 [2019-11-28 12:30:25,404 INFO L226 Difference]: Without dead ends: 80 [2019-11-28 12:30:25,405 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=208, Invalid=442, Unknown=0, NotChecked=0, Total=650 [2019-11-28 12:30:25,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2019-11-28 12:30:25,415 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 46. [2019-11-28 12:30:25,415 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2019-11-28 12:30:25,416 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 56 transitions. [2019-11-28 12:30:25,417 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 56 transitions. Word has length 28 [2019-11-28 12:30:25,417 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-28 12:30:25,417 INFO L462 AbstractCegarLoop]: Abstraction has 46 states and 56 transitions. [2019-11-28 12:30:25,417 INFO L463 AbstractCegarLoop]: Interpolant automaton has 16 states. [2019-11-28 12:30:25,418 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 56 transitions. [2019-11-28 12:30:25,419 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2019-11-28 12:30:25,419 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:30:25,419 INFO L410 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:30:25,630 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 mathsat -unsat_core_generation=3 [2019-11-28 12:30:25,630 INFO L410 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:30:25,638 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:30:25,638 INFO L82 PathProgramCache]: Analyzing trace with hash -1266553509, now seen corresponding path program 2 times [2019-11-28 12:30:25,639 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-28 12:30:25,639 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [430402733] [2019-11-28 12:30:25,639 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 5 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with mathsat -unsat_core_generation=3 [2019-11-28 12:30:25,722 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2019-11-28 12:30:25,722 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-28 12:30:25,730 INFO L255 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 33 conjunts are in the unsatisfiable core [2019-11-28 12:30:25,733 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-28 12:30:26,273 WARN L192 SmtUtils]: Spent 241.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 13 [2019-11-28 12:30:26,351 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2019-11-28 12:30:26,351 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-28 12:30:26,506 WARN L192 SmtUtils]: Spent 153.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2019-11-28 12:30:26,507 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:30:26,507 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:30:26,507 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:31, output treesize:27 [2019-11-28 12:30:26,935 WARN L192 SmtUtils]: Spent 165.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2019-11-28 12:30:27,212 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:30:27,219 INFO L343 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:30:27,220 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 70 treesize of output 32 [2019-11-28 12:30:27,221 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-28 12:30:27,360 WARN L192 SmtUtils]: Spent 138.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2019-11-28 12:30:27,361 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:30:27,362 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-28 12:30:27,363 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:84, output treesize:29 [2019-11-28 12:30:28,201 WARN L192 SmtUtils]: Spent 171.00 ms on a formula simplification that was a NOOP. DAG size: 28 [2019-11-28 12:30:28,204 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:30:28,421 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2019-11-28 12:30:28,421 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-28 12:30:29,494 WARN L192 SmtUtils]: Spent 456.00 ms on a formula simplification that was a NOOP. DAG size: 46 [2019-11-28 12:30:29,903 WARN L192 SmtUtils]: Spent 407.00 ms on a formula simplification that was a NOOP. DAG size: 44 [2019-11-28 12:30:33,569 WARN L192 SmtUtils]: Spent 146.00 ms on a formula simplification that was a NOOP. DAG size: 33 [2019-11-28 12:30:36,778 WARN L192 SmtUtils]: Spent 138.00 ms on a formula simplification that was a NOOP. DAG size: 40 [2019-11-28 12:30:36,789 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 40 [2019-11-28 12:30:36,911 INFO L343 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:30:36,911 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 116 treesize of output 120 [2019-11-28 12:30:36,912 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:30:36,913 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:30:36,914 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:30:36,914 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:30:36,915 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:30:36,916 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:30:36,917 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:30:36,919 INFO L508 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2019-11-28 12:30:37,248 WARN L192 SmtUtils]: Spent 328.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 9 [2019-11-28 12:30:37,249 INFO L588 ElimStorePlain]: treesize reduction 281, result has 3.4 percent of original size [2019-11-28 12:30:37,249 INFO L508 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:30:37,288 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:30:37,288 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:30:37,288 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:44, output treesize:10 [2019-11-28 12:30:38,296 WARN L192 SmtUtils]: Spent 195.00 ms on a formula simplification that was a NOOP. DAG size: 24 [2019-11-28 12:30:38,557 WARN L192 SmtUtils]: Spent 260.00 ms on a formula simplification that was a NOOP. DAG size: 24 [2019-11-28 12:30:40,807 WARN L192 SmtUtils]: Spent 314.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 18 [2019-11-28 12:30:41,996 WARN L192 SmtUtils]: Spent 177.00 ms on a formula simplification that was a NOOP. DAG size: 23 [2019-11-28 12:30:42,078 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2019-11-28 12:30:42,078 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [430402733] [2019-11-28 12:30:42,078 INFO L220 FreeRefinementEngine]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2019-11-28 12:30:42,078 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14, 12] imperfect sequences [] total 24 [2019-11-28 12:30:42,079 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1068064347] [2019-11-28 12:30:42,079 INFO L442 AbstractCegarLoop]: Interpolant automaton has 24 states [2019-11-28 12:30:42,079 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-28 12:30:42,080 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2019-11-28 12:30:42,080 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=482, Unknown=2, NotChecked=0, Total=552 [2019-11-28 12:30:42,080 INFO L87 Difference]: Start difference. First operand 46 states and 56 transitions. Second operand 24 states. [2019-11-28 12:31:00,400 WARN L192 SmtUtils]: Spent 306.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 15 [2019-11-28 12:31:01,610 WARN L192 SmtUtils]: Spent 373.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 24 [2019-11-28 12:31:14,738 WARN L192 SmtUtils]: Spent 8.28 s on a formula simplification that was a NOOP. DAG size: 42 [2019-11-28 12:31:26,433 WARN L192 SmtUtils]: Spent 8.28 s on a formula simplification that was a NOOP. DAG size: 42 [2019-11-28 12:31:31,367 WARN L192 SmtUtils]: Spent 706.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 26 [2019-11-28 12:31:36,476 WARN L192 SmtUtils]: Spent 1.56 s on a formula simplification. DAG size of input: 41 DAG size of output: 39 [2019-11-28 12:31:43,652 WARN L192 SmtUtils]: Spent 1.73 s on a formula simplification. DAG size of input: 44 DAG size of output: 42 [2019-11-28 12:31:49,245 WARN L192 SmtUtils]: Spent 780.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 29 [2019-11-28 12:31:53,497 WARN L192 SmtUtils]: Spent 749.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 29 [2019-11-28 12:31:56,289 WARN L192 SmtUtils]: Spent 357.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 18 [2019-11-28 12:32:00,543 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-28 12:32:00,544 INFO L93 Difference]: Finished difference Result 81 states and 99 transitions. [2019-11-28 12:32:00,550 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2019-11-28 12:32:00,550 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 29 [2019-11-28 12:32:00,551 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-28 12:32:00,555 INFO L225 Difference]: With dead ends: 81 [2019-11-28 12:32:00,555 INFO L226 Difference]: Without dead ends: 79 [2019-11-28 12:32:00,557 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 33 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 57.0s TimeCoverageRelationStatistics Valid=226, Invalid=1249, Unknown=7, NotChecked=0, Total=1482 [2019-11-28 12:32:00,557 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2019-11-28 12:32:00,570 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 60. [2019-11-28 12:32:00,571 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 60 states. [2019-11-28 12:32:00,572 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 76 transitions. [2019-11-28 12:32:00,572 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 76 transitions. Word has length 29 [2019-11-28 12:32:00,573 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-28 12:32:00,573 INFO L462 AbstractCegarLoop]: Abstraction has 60 states and 76 transitions. [2019-11-28 12:32:00,573 INFO L463 AbstractCegarLoop]: Interpolant automaton has 24 states. [2019-11-28 12:32:00,573 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 76 transitions. [2019-11-28 12:32:00,575 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2019-11-28 12:32:00,575 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:32:00,575 INFO L410 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:32:00,775 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 mathsat -unsat_core_generation=3 [2019-11-28 12:32:00,776 INFO L410 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:32:00,776 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:32:00,777 INFO L82 PathProgramCache]: Analyzing trace with hash -1543543150, now seen corresponding path program 1 times [2019-11-28 12:32:00,778 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-28 12:32:00,778 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [461180371] [2019-11-28 12:32:00,778 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 6 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with mathsat -unsat_core_generation=3 [2019-11-28 12:32:00,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-28 12:32:00,979 WARN L253 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 62 conjunts are in the unsatisfiable core [2019-11-28 12:32:00,983 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-28 12:32:01,064 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:32:01,075 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2019-11-28 12:32:01,075 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,122 INFO L588 ElimStorePlain]: treesize reduction 6, result has 81.3 percent of original size [2019-11-28 12:32:01,130 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 6 [2019-11-28 12:32:01,131 INFO L508 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,150 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:32:01,151 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,151 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:33, output treesize:25 [2019-11-28 12:32:01,220 INFO L343 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:32:01,220 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 13 treesize of output 17 [2019-11-28 12:32:01,221 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,247 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:32:01,254 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2019-11-28 12:32:01,255 INFO L508 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,278 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:32:01,279 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-1 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,279 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:42, output treesize:33 [2019-11-28 12:32:01,379 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 32 [2019-11-28 12:32:01,379 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,412 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:32:01,413 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,413 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:59, output treesize:51 [2019-11-28 12:32:01,528 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 28 [2019-11-28 12:32:01,529 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,570 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:32:01,570 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,571 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:52, output treesize:43 [2019-11-28 12:32:01,889 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 61 treesize of output 55 [2019-11-28 12:32:01,890 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,916 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:32:01,917 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,917 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:81, output treesize:71 [2019-11-28 12:32:01,960 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 39 treesize of output 37 [2019-11-28 12:32:01,961 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,984 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:32:01,985 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:32:01,985 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:59, output treesize:51 [2019-11-28 12:32:04,064 WARN L860 $PredicateComparison]: unable to prove that (exists ((downsweep_~tmp~0 (_ BitVec 32))) (= |c_#memory_int| (store |c_old(#memory_int)| |c_downsweep_#in~a.base| (let ((.cse2 (bvadd (bvmul |c_downsweep_#in~left| (_ bv4 32)) |c_downsweep_#in~a.offset|))) (store (let ((.cse0 (select |c_old(#memory_int)| |c_downsweep_#in~a.base|)) (.cse1 (bvadd |c_downsweep_#in~a.offset| (bvmul |c_downsweep_#in~right| (_ bv4 32))))) (store .cse0 .cse1 (bvadd (select .cse0 .cse2) (select .cse0 .cse1)))) .cse2 downsweep_~tmp~0))))) is different from true [2019-11-28 12:32:04,078 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 71 treesize of output 65 [2019-11-28 12:32:04,079 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-28 12:32:04,228 WARN L192 SmtUtils]: Spent 148.00 ms on a formula simplification that was a NOOP. DAG size: 40 [2019-11-28 12:32:04,229 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:32:04,230 INFO L508 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2019-11-28 12:32:04,230 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:91, output treesize:81 [2019-11-28 12:32:06,664 WARN L192 SmtUtils]: Spent 2.10 s on a formula simplification that was a NOOP. DAG size: 42 [2019-11-28 12:32:09,117 WARN L192 SmtUtils]: Spent 2.15 s on a formula simplification that was a NOOP. DAG size: 44 [2019-11-28 12:32:11,588 WARN L192 SmtUtils]: Spent 2.12 s on a formula simplification that was a NOOP. DAG size: 46 [2019-11-28 12:32:14,102 WARN L192 SmtUtils]: Spent 2.11 s on a formula simplification that was a NOOP. DAG size: 49 [2019-11-28 12:32:14,106 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:32:14,258 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-28 12:32:14,258 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-28 12:32:15,687 WARN L192 SmtUtils]: Spent 474.00 ms on a formula simplification that was a NOOP. DAG size: 45 [2019-11-28 12:32:18,193 WARN L192 SmtUtils]: Spent 2.50 s on a formula simplification that was a NOOP. DAG size: 43 [2019-11-28 12:32:21,243 WARN L192 SmtUtils]: Spent 197.00 ms on a formula simplification that was a NOOP. DAG size: 44 [2019-11-28 12:32:27,162 WARN L192 SmtUtils]: Spent 221.00 ms on a formula simplification that was a NOOP. DAG size: 53 [2019-11-28 12:32:29,248 WARN L192 SmtUtils]: Spent 275.00 ms on a formula simplification that was a NOOP. DAG size: 43 [2019-11-28 12:32:29,516 WARN L192 SmtUtils]: Spent 267.00 ms on a formula simplification that was a NOOP. DAG size: 41 [2019-11-28 12:32:31,492 WARN L192 SmtUtils]: Spent 162.00 ms on a formula simplification that was a NOOP. DAG size: 50 [2019-11-28 12:32:33,991 WARN L192 SmtUtils]: Spent 205.00 ms on a formula simplification that was a NOOP. DAG size: 64 [2019-11-28 12:32:55,339 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2019-11-28 12:32:55,339 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-28 12:32:55,480 WARN L192 SmtUtils]: Spent 140.00 ms on a formula simplification that was a NOOP. DAG size: 39 [2019-11-28 12:32:55,481 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:32:55,489 INFO L172 IndexEqualityManager]: detected equality via solver [2019-11-28 12:32:55,490 INFO L508 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2019-11-28 12:32:55,602 WARN L192 SmtUtils]: Spent 111.00 ms on a formula simplification that was a NOOP. DAG size: 29 [2019-11-28 12:32:55,603 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:32:55,604 INFO L508 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-28 12:32:55,604 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:360, output treesize:57 [2019-11-28 12:33:02,348 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2019-11-28 12:33:02,349 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [461180371] [2019-11-28 12:33:02,349 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-28 12:33:02,349 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 21] total 38 [2019-11-28 12:33:02,349 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [313905344] [2019-11-28 12:33:02,350 INFO L442 AbstractCegarLoop]: Interpolant automaton has 38 states [2019-11-28 12:33:02,350 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-28 12:33:02,351 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2019-11-28 12:33:02,352 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=1200, Unknown=6, NotChecked=70, Total=1406 [2019-11-28 12:33:02,352 INFO L87 Difference]: Start difference. First operand 60 states and 76 transitions. Second operand 38 states. [2019-11-28 12:33:04,750 WARN L192 SmtUtils]: Spent 255.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 34 [2019-11-28 12:33:06,761 WARN L192 SmtUtils]: Spent 317.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 42 [2019-11-28 12:33:09,214 WARN L192 SmtUtils]: Spent 221.00 ms on a formula simplification that was a NOOP. DAG size: 39 [2019-11-28 12:33:11,253 WARN L192 SmtUtils]: Spent 298.00 ms on a formula simplification that was a NOOP. DAG size: 42 [2019-11-28 12:33:11,993 WARN L192 SmtUtils]: Spent 129.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 47 [2019-11-28 12:33:21,581 WARN L192 SmtUtils]: Spent 4.44 s on a formula simplification that was a NOOP. DAG size: 75 [2019-11-28 12:33:31,907 WARN L192 SmtUtils]: Spent 767.00 ms on a formula simplification that was a NOOP. DAG size: 71 [2019-11-28 12:33:32,696 WARN L192 SmtUtils]: Spent 137.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 47 [2019-11-28 12:33:43,723 WARN L192 SmtUtils]: Spent 3.83 s on a formula simplification that was a NOOP. DAG size: 98 [2019-11-28 12:33:52,920 WARN L192 SmtUtils]: Spent 1.61 s on a formula simplification that was a NOOP. DAG size: 90 [2019-11-28 12:33:53,698 WARN L192 SmtUtils]: Spent 130.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 50 [2019-11-28 12:33:58,794 WARN L192 SmtUtils]: Spent 923.00 ms on a formula simplification that was a NOOP. DAG size: 70 [2019-11-28 12:34:05,897 WARN L192 SmtUtils]: Spent 1.05 s on a formula simplification that was a NOOP. DAG size: 80 [2019-11-28 12:34:16,905 WARN L192 SmtUtils]: Spent 696.00 ms on a formula simplification that was a NOOP. DAG size: 61 [2019-11-28 12:34:54,050 WARN L192 SmtUtils]: Spent 6.83 s on a formula simplification that was a NOOP. DAG size: 62 [2019-11-28 12:34:57,720 WARN L860 $PredicateComparison]: unable to prove that (and (or (not (= (bvadd |c_downsweep_#in~left| (_ bv1 32)) (bvsdiv (bvadd |c_downsweep_#in~right| (_ bv1 32)) (_ bv2 32)))) (forall ((v_ULTIMATE.start_main_~a0~0.offset_BEFORE_CALL_3 (_ BitVec 32)) (v_ULTIMATE.start_main_~a0~0.base_BEFORE_CALL_3 (_ BitVec 32))) (or (= (select (select |c_#memory_int| v_ULTIMATE.start_main_~a0~0.base_BEFORE_CALL_3) v_ULTIMATE.start_main_~a0~0.offset_BEFORE_CALL_3) (select (select |c_#memory_int| |c_downsweep_#in~a.base|) (bvadd |c_downsweep_#in~a.offset| (_ bv4 32)))) (exists ((v_downsweep_~tmp~0_17 (_ BitVec 32))) (not (let ((.cse0 (let ((.cse3 (bvadd (bvmul (bvsdiv (bvadd |c_downsweep_#in~right| (_ bv1 32)) (_ bv2 32)) (_ bv4 32)) |c_downsweep_#in~a.offset| (_ bv4294967292 32)))) (store (let ((.cse1 (select |c_old(#memory_int)| |c_downsweep_#in~a.base|)) (.cse2 (bvadd |c_downsweep_#in~a.offset| (bvmul |c_downsweep_#in~right| (_ bv4 32))))) (store .cse1 .cse2 (bvadd (select .cse1 .cse3) (select .cse1 .cse2)))) .cse3 v_downsweep_~tmp~0_17)))) (= (select .cse0 (bvadd |c_downsweep_#in~a.offset| (_ bv4 32))) (select (select (store |c_old(#memory_int)| |c_downsweep_#in~a.base| .cse0) v_ULTIMATE.start_main_~a0~0.base_BEFORE_CALL_3) v_ULTIMATE.start_main_~a0~0.offset_BEFORE_CALL_3)))))))) (exists ((downsweep_~tmp~0 (_ BitVec 32))) (= |c_#memory_int| (store |c_old(#memory_int)| |c_downsweep_#in~a.base| (let ((.cse6 (bvadd (bvmul |c_downsweep_#in~left| (_ bv4 32)) |c_downsweep_#in~a.offset|))) (store (let ((.cse4 (select |c_old(#memory_int)| |c_downsweep_#in~a.base|)) (.cse5 (bvadd |c_downsweep_#in~a.offset| (bvmul |c_downsweep_#in~right| (_ bv4 32))))) (store .cse4 .cse5 (bvadd (select .cse4 .cse6) (select .cse4 .cse5)))) .cse6 downsweep_~tmp~0)))))) is different from true [2019-11-28 12:35:08,913 WARN L192 SmtUtils]: Spent 4.39 s on a formula simplification that was a NOOP. DAG size: 69 [2019-11-28 12:35:15,772 WARN L192 SmtUtils]: Spent 4.54 s on a formula simplification that was a NOOP. DAG size: 72 [2019-11-28 12:35:25,646 WARN L192 SmtUtils]: Spent 4.42 s on a formula simplification that was a NOOP. DAG size: 86 [2019-11-28 12:35:32,877 WARN L192 SmtUtils]: Spent 4.40 s on a formula simplification that was a NOOP. DAG size: 86 [2019-11-28 12:35:42,319 WARN L192 SmtUtils]: Spent 4.33 s on a formula simplification that was a NOOP. DAG size: 77 [2019-11-28 12:35:46,590 WARN L192 SmtUtils]: Spent 2.18 s on a formula simplification that was a NOOP. DAG size: 58 [2019-11-28 12:35:50,746 WARN L192 SmtUtils]: Spent 2.14 s on a formula simplification that was a NOOP. DAG size: 46 [2019-11-28 12:35:54,204 WARN L192 SmtUtils]: Spent 2.13 s on a formula simplification that was a NOOP. DAG size: 45 [2019-11-28 12:36:04,073 WARN L192 SmtUtils]: Spent 902.00 ms on a formula simplification that was a NOOP. DAG size: 72 [2019-11-28 12:36:16,117 WARN L192 SmtUtils]: Spent 6.23 s on a formula simplification that was a NOOP. DAG size: 55 [2019-11-28 12:36:26,320 WARN L192 SmtUtils]: Spent 7.89 s on a formula simplification. DAG size of input: 112 DAG size of output: 103 [2019-11-28 12:36:41,389 WARN L192 SmtUtils]: Spent 8.02 s on a formula simplification. DAG size of input: 115 DAG size of output: 106 [2019-11-28 12:36:42,408 WARN L192 SmtUtils]: Spent 325.00 ms on a formula simplification that was a NOOP. DAG size: 45 [2019-11-28 12:36:52,202 WARN L192 SmtUtils]: Spent 124.00 ms on a formula simplification that was a NOOP. DAG size: 38 [2019-11-28 12:36:53,872 WARN L192 SmtUtils]: Spent 476.00 ms on a formula simplification that was a NOOP. DAG size: 53 [2019-11-28 12:36:55,885 WARN L192 SmtUtils]: Spent 401.00 ms on a formula simplification that was a NOOP. DAG size: 70 [2019-11-28 12:36:58,428 WARN L192 SmtUtils]: Spent 409.00 ms on a formula simplification that was a NOOP. DAG size: 73 [2019-11-28 12:37:00,732 WARN L192 SmtUtils]: Spent 392.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2019-11-28 12:37:02,707 WARN L192 SmtUtils]: Spent 398.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2019-11-28 12:37:04,440 WARN L192 SmtUtils]: Spent 373.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2019-11-28 12:37:07,677 WARN L192 SmtUtils]: Spent 459.00 ms on a formula simplification that was a NOOP. DAG size: 56 [2019-11-28 12:37:09,970 WARN L192 SmtUtils]: Spent 475.00 ms on a formula simplification that was a NOOP. DAG size: 56 [2019-11-28 12:37:18,656 WARN L192 SmtUtils]: Spent 322.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 45 [2019-11-28 12:37:18,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-28 12:37:18,869 INFO L93 Difference]: Finished difference Result 178 states and 219 transitions. [2019-11-28 12:37:18,877 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2019-11-28 12:37:18,877 INFO L78 Accepts]: Start accepts. Automaton has 38 states. Word has length 33 [2019-11-28 12:37:18,878 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-28 12:37:18,880 INFO L225 Difference]: With dead ends: 178 [2019-11-28 12:37:18,880 INFO L226 Difference]: Without dead ends: 176 [2019-11-28 12:37:18,882 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 27 SyntacticMatches, 3 SemanticMatches, 79 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 1025 ImplicationChecksByTransitivity, 213.0s TimeCoverageRelationStatistics Valid=674, Invalid=5482, Unknown=14, NotChecked=310, Total=6480 [2019-11-28 12:37:18,883 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 176 states. [2019-11-28 12:37:18,907 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 176 to 99. [2019-11-28 12:37:18,907 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 99 states. [2019-11-28 12:37:18,909 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 126 transitions. [2019-11-28 12:37:18,909 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 126 transitions. Word has length 33 [2019-11-28 12:37:18,910 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-28 12:37:18,910 INFO L462 AbstractCegarLoop]: Abstraction has 99 states and 126 transitions. [2019-11-28 12:37:18,910 INFO L463 AbstractCegarLoop]: Interpolant automaton has 38 states. [2019-11-28 12:37:18,910 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 126 transitions. [2019-11-28 12:37:18,912 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2019-11-28 12:37:18,912 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:37:18,913 INFO L410 BasicCegarLoop]: trace histogram [4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:37:19,116 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 mathsat -unsat_core_generation=3 [2019-11-28 12:37:19,117 INFO L410 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:37:19,117 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:37:19,117 INFO L82 PathProgramCache]: Analyzing trace with hash 619891810, now seen corresponding path program 2 times [2019-11-28 12:37:19,118 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-28 12:37:19,118 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [316996499] [2019-11-28 12:37:19,119 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 7 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with mathsat -unsat_core_generation=3 [2019-11-28 12:37:19,220 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-28 12:37:19,220 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-28 12:37:19,229 INFO L255 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 11 conjunts are in the unsatisfiable core [2019-11-28 12:37:19,231 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-28 12:37:19,346 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2019-11-28 12:37:19,347 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-28 12:37:19,628 WARN L192 SmtUtils]: Spent 254.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2019-11-28 12:37:20,044 WARN L192 SmtUtils]: Spent 415.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2019-11-28 12:37:21,135 WARN L192 SmtUtils]: Spent 145.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2019-11-28 12:37:22,366 WARN L192 SmtUtils]: Spent 152.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2019-11-28 12:37:23,233 WARN L192 SmtUtils]: Spent 110.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2019-11-28 12:37:23,798 WARN L192 SmtUtils]: Spent 131.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2019-11-28 12:37:23,830 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2019-11-28 12:37:23,830 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [316996499] [2019-11-28 12:37:23,830 INFO L220 FreeRefinementEngine]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2019-11-28 12:37:23,830 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 12 [2019-11-28 12:37:23,830 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1070325902] [2019-11-28 12:37:23,831 INFO L442 AbstractCegarLoop]: Interpolant automaton has 7 states [2019-11-28 12:37:23,831 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-28 12:37:23,831 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2019-11-28 12:37:23,832 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2019-11-28 12:37:23,832 INFO L87 Difference]: Start difference. First operand 99 states and 126 transitions. Second operand 7 states. [2019-11-28 12:37:26,446 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-28 12:37:26,446 INFO L93 Difference]: Finished difference Result 137 states and 169 transitions. [2019-11-28 12:37:26,466 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2019-11-28 12:37:26,466 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 36 [2019-11-28 12:37:26,466 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-28 12:37:26,468 INFO L225 Difference]: With dead ends: 137 [2019-11-28 12:37:26,468 INFO L226 Difference]: Without dead ends: 102 [2019-11-28 12:37:26,469 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 59 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2019-11-28 12:37:26,469 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2019-11-28 12:37:26,486 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 82. [2019-11-28 12:37:26,487 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 82 states. [2019-11-28 12:37:26,488 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 100 transitions. [2019-11-28 12:37:26,488 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 100 transitions. Word has length 36 [2019-11-28 12:37:26,489 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-28 12:37:26,489 INFO L462 AbstractCegarLoop]: Abstraction has 82 states and 100 transitions. [2019-11-28 12:37:26,489 INFO L463 AbstractCegarLoop]: Interpolant automaton has 7 states. [2019-11-28 12:37:26,489 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 100 transitions. [2019-11-28 12:37:26,499 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2019-11-28 12:37:26,499 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:37:26,500 INFO L410 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:37:26,701 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 mathsat -unsat_core_generation=3 [2019-11-28 12:37:26,701 INFO L410 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:37:26,702 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:37:26,702 INFO L82 PathProgramCache]: Analyzing trace with hash 1468501563, now seen corresponding path program 1 times [2019-11-28 12:37:26,702 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-28 12:37:26,702 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1385638201] [2019-11-28 12:37:26,702 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 8 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with mathsat -unsat_core_generation=3 [2019-11-28 12:37:26,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-28 12:37:26,787 INFO L255 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 12 conjunts are in the unsatisfiable core [2019-11-28 12:37:26,789 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-28 12:37:26,843 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:37:26,937 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2019-11-28 12:37:26,937 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-28 12:37:27,148 WARN L192 SmtUtils]: Spent 183.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-28 12:37:27,311 WARN L192 SmtUtils]: Spent 162.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-28 12:37:28,630 WARN L192 SmtUtils]: Spent 136.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2019-11-28 12:37:30,056 WARN L192 SmtUtils]: Spent 141.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2019-11-28 12:37:30,990 WARN L192 SmtUtils]: Spent 122.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2019-11-28 12:37:31,543 WARN L192 SmtUtils]: Spent 122.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2019-11-28 12:37:32,194 WARN L192 SmtUtils]: Spent 133.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2019-11-28 12:37:32,217 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2019-11-28 12:37:32,217 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1385638201] [2019-11-28 12:37:32,218 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-28 12:37:32,218 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2019-11-28 12:37:32,218 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [525381063] [2019-11-28 12:37:32,218 INFO L442 AbstractCegarLoop]: Interpolant automaton has 14 states [2019-11-28 12:37:32,218 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-28 12:37:32,219 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2019-11-28 12:37:32,219 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2019-11-28 12:37:32,219 INFO L87 Difference]: Start difference. First operand 82 states and 100 transitions. Second operand 14 states. [2019-11-28 12:37:32,822 WARN L192 SmtUtils]: Spent 132.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 22 [2019-11-28 12:37:33,414 WARN L192 SmtUtils]: Spent 166.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 30 [2019-11-28 12:37:36,469 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-28 12:37:36,469 INFO L93 Difference]: Finished difference Result 98 states and 118 transitions. [2019-11-28 12:37:36,478 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2019-11-28 12:37:36,478 INFO L78 Accepts]: Start accepts. Automaton has 14 states. Word has length 39 [2019-11-28 12:37:36,478 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-28 12:37:36,479 INFO L225 Difference]: With dead ends: 98 [2019-11-28 12:37:36,479 INFO L226 Difference]: Without dead ends: 91 [2019-11-28 12:37:36,480 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 64 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 6.0s TimeCoverageRelationStatistics Valid=70, Invalid=236, Unknown=0, NotChecked=0, Total=306 [2019-11-28 12:37:36,480 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2019-11-28 12:37:36,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 84. [2019-11-28 12:37:36,495 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 84 states. [2019-11-28 12:37:36,496 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 102 transitions. [2019-11-28 12:37:36,496 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 102 transitions. Word has length 39 [2019-11-28 12:37:36,497 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-28 12:37:36,497 INFO L462 AbstractCegarLoop]: Abstraction has 84 states and 102 transitions. [2019-11-28 12:37:36,497 INFO L463 AbstractCegarLoop]: Interpolant automaton has 14 states. [2019-11-28 12:37:36,497 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 102 transitions. [2019-11-28 12:37:36,499 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2019-11-28 12:37:36,499 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:37:36,499 INFO L410 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:37:36,710 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 mathsat -unsat_core_generation=3 [2019-11-28 12:37:36,711 INFO L410 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:37:36,711 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:37:36,712 INFO L82 PathProgramCache]: Analyzing trace with hash -1965818131, now seen corresponding path program 1 times [2019-11-28 12:37:36,712 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-28 12:37:36,713 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [624838792] [2019-11-28 12:37:36,713 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 9 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with mathsat -unsat_core_generation=3 [2019-11-28 12:37:36,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-28 12:37:36,799 INFO L255 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 12 conjunts are in the unsatisfiable core [2019-11-28 12:37:36,802 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-28 12:37:36,870 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:37:36,980 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2019-11-28 12:37:36,980 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-28 12:37:37,289 WARN L192 SmtUtils]: Spent 273.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-28 12:37:37,498 WARN L192 SmtUtils]: Spent 208.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-28 12:37:38,766 WARN L192 SmtUtils]: Spent 127.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2019-11-28 12:37:40,390 WARN L192 SmtUtils]: Spent 152.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2019-11-28 12:37:41,554 WARN L192 SmtUtils]: Spent 113.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2019-11-28 12:37:42,112 WARN L192 SmtUtils]: Spent 108.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2019-11-28 12:37:42,740 WARN L192 SmtUtils]: Spent 134.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2019-11-28 12:37:42,763 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2019-11-28 12:37:42,763 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [624838792] [2019-11-28 12:37:42,763 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-28 12:37:42,763 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2019-11-28 12:37:42,764 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [700436911] [2019-11-28 12:37:42,764 INFO L442 AbstractCegarLoop]: Interpolant automaton has 14 states [2019-11-28 12:37:42,764 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-28 12:37:42,764 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2019-11-28 12:37:42,765 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2019-11-28 12:37:42,765 INFO L87 Difference]: Start difference. First operand 84 states and 102 transitions. Second operand 14 states. [2019-11-28 12:37:43,354 WARN L192 SmtUtils]: Spent 132.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 22 [2019-11-28 12:37:43,956 WARN L192 SmtUtils]: Spent 165.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 30 [2019-11-28 12:37:46,140 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-28 12:37:46,141 INFO L93 Difference]: Finished difference Result 109 states and 130 transitions. [2019-11-28 12:37:46,148 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2019-11-28 12:37:46,148 INFO L78 Accepts]: Start accepts. Automaton has 14 states. Word has length 41 [2019-11-28 12:37:46,149 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-28 12:37:46,150 INFO L225 Difference]: With dead ends: 109 [2019-11-28 12:37:46,150 INFO L226 Difference]: Without dead ends: 88 [2019-11-28 12:37:46,151 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 68 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 6.4s TimeCoverageRelationStatistics Valid=70, Invalid=236, Unknown=0, NotChecked=0, Total=306 [2019-11-28 12:37:46,151 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2019-11-28 12:37:46,166 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 82. [2019-11-28 12:37:46,166 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 82 states. [2019-11-28 12:37:46,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 98 transitions. [2019-11-28 12:37:46,170 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 98 transitions. Word has length 41 [2019-11-28 12:37:46,171 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-28 12:37:46,171 INFO L462 AbstractCegarLoop]: Abstraction has 82 states and 98 transitions. [2019-11-28 12:37:46,171 INFO L463 AbstractCegarLoop]: Interpolant automaton has 14 states. [2019-11-28 12:37:46,172 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 98 transitions. [2019-11-28 12:37:46,175 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2019-11-28 12:37:46,175 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:37:46,176 INFO L410 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:37:46,388 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 mathsat -unsat_core_generation=3 [2019-11-28 12:37:46,388 INFO L410 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:37:46,388 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:37:46,389 INFO L82 PathProgramCache]: Analyzing trace with hash -1690437395, now seen corresponding path program 2 times [2019-11-28 12:37:46,389 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-28 12:37:46,389 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1766072129] [2019-11-28 12:37:46,390 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 10 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with mathsat -unsat_core_generation=3 [2019-11-28 12:37:46,477 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2019-11-28 12:37:46,477 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-28 12:37:46,482 INFO L255 TraceCheckSpWp]: Trace formula consists of 91 conjuncts, 27 conjunts are in the unsatisfiable core [2019-11-28 12:37:46,484 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-28 12:37:46,522 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2019-11-28 12:37:46,523 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-28 12:37:46,542 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:37:46,542 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:37:46,542 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:26, output treesize:22 [2019-11-28 12:37:46,840 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:37:46,848 INFO L343 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:37:46,848 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 70 treesize of output 32 [2019-11-28 12:37:46,849 INFO L508 ElimStorePlain]: Start of recursive call 2: 1 dim-0 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-28 12:37:47,248 WARN L192 SmtUtils]: Spent 398.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 29 [2019-11-28 12:37:47,248 INFO L588 ElimStorePlain]: treesize reduction 3, result has 94.9 percent of original size [2019-11-28 12:37:47,249 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2019-11-28 12:37:47,249 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:87, output treesize:56 [2019-11-28 12:37:47,719 WARN L192 SmtUtils]: Spent 134.00 ms on a formula simplification that was a NOOP. DAG size: 31 [2019-11-28 12:37:48,256 WARN L192 SmtUtils]: Spent 222.00 ms on a formula simplification that was a NOOP. DAG size: 35 [2019-11-28 12:37:48,257 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:37:48,447 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2019-11-28 12:37:48,448 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-28 12:37:49,529 WARN L192 SmtUtils]: Spent 501.00 ms on a formula simplification that was a NOOP. DAG size: 50 [2019-11-28 12:37:50,249 WARN L192 SmtUtils]: Spent 718.00 ms on a formula simplification that was a NOOP. DAG size: 48 [2019-11-28 12:37:51,241 WARN L192 SmtUtils]: Spent 128.00 ms on a formula simplification that was a NOOP. DAG size: 25 [2019-11-28 12:37:54,322 WARN L192 SmtUtils]: Spent 180.00 ms on a formula simplification that was a NOOP. DAG size: 36 [2019-11-28 12:37:59,440 WARN L192 SmtUtils]: Spent 219.00 ms on a formula simplification that was a NOOP. DAG size: 40 [2019-11-28 12:38:04,075 WARN L192 SmtUtils]: Spent 1.19 s on a formula simplification. DAG size of input: 44 DAG size of output: 41 [2019-11-28 12:38:04,124 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 40 [2019-11-28 12:38:04,296 WARN L192 SmtUtils]: Spent 106.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2019-11-28 12:38:04,296 INFO L343 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:38:04,296 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 116 treesize of output 120 [2019-11-28 12:38:04,297 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:38:04,297 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:38:04,297 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:38:04,298 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:38:04,298 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:38:04,298 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:38:04,301 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:38:04,306 INFO L508 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2019-11-28 12:38:04,614 WARN L192 SmtUtils]: Spent 307.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 9 [2019-11-28 12:38:04,615 INFO L588 ElimStorePlain]: treesize reduction 196, result has 4.9 percent of original size [2019-11-28 12:38:04,615 INFO L508 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:38:04,711 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:38:04,712 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:38:04,712 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:52, output treesize:18 [2019-11-28 12:38:05,775 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2019-11-28 12:38:05,775 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1766072129] [2019-11-28 12:38:05,775 INFO L220 FreeRefinementEngine]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2019-11-28 12:38:05,775 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12, 10] imperfect sequences [] total 20 [2019-11-28 12:38:05,775 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2045798927] [2019-11-28 12:38:05,776 INFO L442 AbstractCegarLoop]: Interpolant automaton has 20 states [2019-11-28 12:38:05,776 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-28 12:38:05,776 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2019-11-28 12:38:05,776 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=326, Unknown=4, NotChecked=0, Total=380 [2019-11-28 12:38:05,777 INFO L87 Difference]: Start difference. First operand 82 states and 98 transitions. Second operand 20 states. [2019-11-28 12:38:07,457 WARN L192 SmtUtils]: Spent 137.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 3 [2019-11-28 12:38:34,701 WARN L192 SmtUtils]: Spent 25.25 s on a formula simplification. DAG size of input: 54 DAG size of output: 51 [2019-11-28 12:38:57,556 WARN L192 SmtUtils]: Spent 19.43 s on a formula simplification. DAG size of input: 62 DAG size of output: 48 [2019-11-28 12:39:25,488 WARN L192 SmtUtils]: Spent 26.37 s on a formula simplification. DAG size of input: 69 DAG size of output: 66 [2019-11-28 12:39:27,845 WARN L192 SmtUtils]: Spent 170.00 ms on a formula simplification that was a NOOP. DAG size: 35 [2019-11-28 12:39:29,949 WARN L192 SmtUtils]: Spent 751.00 ms on a formula simplification that was a NOOP. DAG size: 52 [2019-11-28 12:39:31,975 WARN L192 SmtUtils]: Spent 789.00 ms on a formula simplification that was a NOOP. DAG size: 55 [2019-11-28 12:39:35,265 WARN L192 SmtUtils]: Spent 174.00 ms on a formula simplification that was a NOOP. DAG size: 38 [2019-11-28 12:39:36,592 WARN L192 SmtUtils]: Spent 179.00 ms on a formula simplification that was a NOOP. DAG size: 38 [2019-11-28 12:39:37,782 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-28 12:39:37,783 INFO L93 Difference]: Finished difference Result 97 states and 113 transitions. [2019-11-28 12:39:37,783 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2019-11-28 12:39:37,784 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 43 [2019-11-28 12:39:37,784 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-28 12:39:37,785 INFO L225 Difference]: With dead ends: 97 [2019-11-28 12:39:37,785 INFO L226 Difference]: Without dead ends: 95 [2019-11-28 12:39:37,786 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 132 ImplicationChecksByTransitivity, 97.6s TimeCoverageRelationStatistics Valid=159, Invalid=829, Unknown=4, NotChecked=0, Total=992 [2019-11-28 12:39:37,786 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2019-11-28 12:39:37,797 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 83. [2019-11-28 12:39:37,797 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 83 states. [2019-11-28 12:39:37,798 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 99 transitions. [2019-11-28 12:39:37,798 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 99 transitions. Word has length 43 [2019-11-28 12:39:37,799 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-28 12:39:37,799 INFO L462 AbstractCegarLoop]: Abstraction has 83 states and 99 transitions. [2019-11-28 12:39:37,799 INFO L463 AbstractCegarLoop]: Interpolant automaton has 20 states. [2019-11-28 12:39:37,799 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 99 transitions. [2019-11-28 12:39:37,800 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2019-11-28 12:39:37,800 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:39:37,801 INFO L410 BasicCegarLoop]: trace histogram [5, 5, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:39:38,002 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 mathsat -unsat_core_generation=3 [2019-11-28 12:39:38,003 INFO L410 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:39:38,003 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:39:38,003 INFO L82 PathProgramCache]: Analyzing trace with hash -1612034515, now seen corresponding path program 1 times [2019-11-28 12:39:38,004 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-28 12:39:38,004 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [4532715] [2019-11-28 12:39:38,005 INFO L94 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 11 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with mathsat -unsat_core_generation=3 [2019-11-28 12:39:38,117 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2019-11-28 12:39:38,131 INFO L255 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 12 conjunts are in the unsatisfiable core [2019-11-28 12:39:38,133 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-28 12:39:38,229 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:39:38,324 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 57 trivial. 0 not checked. [2019-11-28 12:39:38,324 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-28 12:39:38,638 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 57 trivial. 0 not checked. [2019-11-28 12:39:38,638 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [4532715] [2019-11-28 12:39:38,639 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-28 12:39:38,639 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 20 [2019-11-28 12:39:38,639 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [153951260] [2019-11-28 12:39:38,640 INFO L442 AbstractCegarLoop]: Interpolant automaton has 20 states [2019-11-28 12:39:38,640 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-28 12:39:38,640 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2019-11-28 12:39:38,640 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=287, Unknown=0, NotChecked=0, Total=380 [2019-11-28 12:39:38,640 INFO L87 Difference]: Start difference. First operand 83 states and 99 transitions. Second operand 20 states. [2019-11-28 12:39:40,694 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-28 12:39:40,695 INFO L93 Difference]: Finished difference Result 177 states and 216 transitions. [2019-11-28 12:39:40,695 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2019-11-28 12:39:40,696 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 63 [2019-11-28 12:39:40,696 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-28 12:39:40,697 INFO L225 Difference]: With dead ends: 177 [2019-11-28 12:39:40,697 INFO L226 Difference]: Without dead ends: 142 [2019-11-28 12:39:40,699 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 106 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 212 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=367, Invalid=1039, Unknown=0, NotChecked=0, Total=1406 [2019-11-28 12:39:40,700 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2019-11-28 12:39:40,715 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 92. [2019-11-28 12:39:40,715 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 92 states. [2019-11-28 12:39:40,716 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 109 transitions. [2019-11-28 12:39:40,716 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 109 transitions. Word has length 63 [2019-11-28 12:39:40,716 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-28 12:39:40,716 INFO L462 AbstractCegarLoop]: Abstraction has 92 states and 109 transitions. [2019-11-28 12:39:40,716 INFO L463 AbstractCegarLoop]: Interpolant automaton has 20 states. [2019-11-28 12:39:40,716 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 109 transitions. [2019-11-28 12:39:40,717 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2019-11-28 12:39:40,717 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:39:40,718 INFO L410 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:39:40,920 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 mathsat -unsat_core_generation=3 [2019-11-28 12:39:40,921 INFO L410 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:39:40,921 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:39:40,921 INFO L82 PathProgramCache]: Analyzing trace with hash -781396103, now seen corresponding path program 2 times [2019-11-28 12:39:40,922 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-28 12:39:40,922 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1929427646] [2019-11-28 12:39:40,922 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 12 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with mathsat -unsat_core_generation=3 [2019-11-28 12:39:41,091 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2019-11-28 12:39:41,091 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-28 12:39:41,110 INFO L255 TraceCheckSpWp]: Trace formula consists of 200 conjuncts, 19 conjunts are in the unsatisfiable core [2019-11-28 12:39:41,113 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-28 12:39:41,210 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:39:42,338 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 10 proven. 15 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2019-11-28 12:39:42,338 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-28 12:39:42,578 WARN L192 SmtUtils]: Spent 213.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-28 12:39:42,760 WARN L192 SmtUtils]: Spent 181.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-28 12:39:43,125 WARN L192 SmtUtils]: Spent 361.00 ms on a formula simplification that was a NOOP. DAG size: 26 [2019-11-28 12:39:43,327 WARN L192 SmtUtils]: Spent 201.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2019-11-28 12:39:43,977 WARN L192 SmtUtils]: Spent 649.00 ms on a formula simplification that was a NOOP. DAG size: 24 [2019-11-28 12:39:44,609 WARN L192 SmtUtils]: Spent 630.00 ms on a formula simplification that was a NOOP. DAG size: 24 [2019-11-28 12:39:50,985 WARN L192 SmtUtils]: Spent 562.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-28 12:39:51,246 WARN L192 SmtUtils]: Spent 217.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-28 12:39:51,459 WARN L192 SmtUtils]: Spent 211.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2019-11-28 12:39:58,875 WARN L192 SmtUtils]: Spent 605.00 ms on a formula simplification that was a NOOP. DAG size: 25 [2019-11-28 12:39:58,876 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:40:03,546 WARN L192 SmtUtils]: Spent 552.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2019-11-28 12:40:11,894 WARN L192 SmtUtils]: Spent 620.00 ms on a formula simplification that was a NOOP. DAG size: 27 [2019-11-28 12:40:14,004 WARN L860 $PredicateComparison]: unable to prove that (let ((.cse1 (bvsdiv (bvadd |c_downsweep_#in~right| (_ bv1 32)) (_ bv2 32)))) (or (let ((.cse0 (bvadd .cse1 (_ bv4294967295 32)))) (bvsgt .cse0 (bvadd .cse1 (bvneg (bvsdiv (bvadd (bvneg .cse0) |c_downsweep_#in~right|) (_ bv2 32)))))) (not (= (bvadd |c_downsweep_#in~left| (_ bv1 32)) .cse1)) (not (bvsgt |c_downsweep_#in~left| (bvadd (bvneg (bvsdiv (bvadd (bvneg |c_downsweep_#in~left|) |c_downsweep_#in~right|) (_ bv2 32))) |c_downsweep_#in~left| (_ bv1 32)))))) is different from true [2019-11-28 12:40:17,665 WARN L192 SmtUtils]: Spent 325.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2019-11-28 12:40:19,750 WARN L192 SmtUtils]: Spent 324.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2019-11-28 12:40:22,924 WARN L192 SmtUtils]: Spent 474.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2019-11-28 12:40:26,174 WARN L192 SmtUtils]: Spent 463.00 ms on a formula simplification that was a NOOP. DAG size: 26 [2019-11-28 12:40:26,227 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 10 proven. 16 refuted. 4 times theorem prover too weak. 46 trivial. 0 not checked. [2019-11-28 12:40:26,227 INFO L348 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1929427646] [2019-11-28 12:40:26,227 INFO L220 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2019-11-28 12:40:26,227 INFO L233 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 13] total 22 [2019-11-28 12:40:26,228 INFO L156 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [43414260] [2019-11-28 12:40:26,228 INFO L442 AbstractCegarLoop]: Interpolant automaton has 22 states [2019-11-28 12:40:26,228 INFO L143 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2019-11-28 12:40:26,229 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2019-11-28 12:40:26,229 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=355, Unknown=6, NotChecked=38, Total=462 [2019-11-28 12:40:26,229 INFO L87 Difference]: Start difference. First operand 92 states and 109 transitions. Second operand 22 states. [2019-11-28 12:40:29,464 WARN L192 SmtUtils]: Spent 373.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 24 [2019-11-28 12:40:33,824 WARN L192 SmtUtils]: Spent 1.50 s on a formula simplification. DAG size of input: 37 DAG size of output: 37 [2019-11-28 12:40:36,877 WARN L192 SmtUtils]: Spent 628.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 32 [2019-11-28 12:40:42,067 WARN L192 SmtUtils]: Spent 1.53 s on a formula simplification. DAG size of input: 23 DAG size of output: 21 [2019-11-28 12:40:44,897 WARN L192 SmtUtils]: Spent 773.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 40 [2019-11-28 12:40:48,672 WARN L192 SmtUtils]: Spent 1.11 s on a formula simplification that was a NOOP. DAG size: 31 [2019-11-28 12:41:02,630 WARN L192 SmtUtils]: Spent 5.62 s on a formula simplification. DAG size of input: 30 DAG size of output: 7 [2019-11-28 12:41:24,306 WARN L192 SmtUtils]: Spent 18.35 s on a formula simplification that was a NOOP. DAG size: 41 [2019-11-28 12:42:15,659 WARN L192 SmtUtils]: Spent 9.79 s on a formula simplification that was a NOOP. DAG size: 34 [2019-11-28 12:42:41,321 WARN L192 SmtUtils]: Spent 9.17 s on a formula simplification that was a NOOP. DAG size: 35 [2019-11-28 12:42:50,903 WARN L192 SmtUtils]: Spent 6.62 s on a formula simplification. DAG size of input: 37 DAG size of output: 24 [2019-11-28 12:43:22,077 WARN L192 SmtUtils]: Spent 8.64 s on a formula simplification that was a NOOP. DAG size: 31 [2019-11-28 12:43:43,667 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2019-11-28 12:43:43,668 INFO L93 Difference]: Finished difference Result 141 states and 173 transitions. [2019-11-28 12:43:43,676 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2019-11-28 12:43:43,676 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 66 [2019-11-28 12:43:43,676 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2019-11-28 12:43:43,678 INFO L225 Difference]: With dead ends: 141 [2019-11-28 12:43:43,678 INFO L226 Difference]: Without dead ends: 129 [2019-11-28 12:43:43,679 INFO L630 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 113 SyntacticMatches, 2 SemanticMatches, 34 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 125 ImplicationChecksByTransitivity, 160.5s TimeCoverageRelationStatistics Valid=202, Invalid=975, Unknown=17, NotChecked=66, Total=1260 [2019-11-28 12:43:43,679 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2019-11-28 12:43:43,695 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 110. [2019-11-28 12:43:43,696 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 110 states. [2019-11-28 12:43:43,696 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 132 transitions. [2019-11-28 12:43:43,696 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 132 transitions. Word has length 66 [2019-11-28 12:43:43,697 INFO L84 Accepts]: Finished accepts. word is rejected. [2019-11-28 12:43:43,697 INFO L462 AbstractCegarLoop]: Abstraction has 110 states and 132 transitions. [2019-11-28 12:43:43,697 INFO L463 AbstractCegarLoop]: Interpolant automaton has 22 states. [2019-11-28 12:43:43,697 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 132 transitions. [2019-11-28 12:43:43,698 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2019-11-28 12:43:43,698 INFO L402 BasicCegarLoop]: Found error trace [2019-11-28 12:43:43,699 INFO L410 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2019-11-28 12:43:43,900 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 mathsat -unsat_core_generation=3 [2019-11-28 12:43:43,901 INFO L410 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2019-11-28 12:43:43,901 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2019-11-28 12:43:43,901 INFO L82 PathProgramCache]: Analyzing trace with hash 653476761, now seen corresponding path program 3 times [2019-11-28 12:43:43,902 INFO L163 FreeRefinementEngine]: Executing refinement strategy WOLF [2019-11-28 12:43:43,902 INFO L348 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1463965588] [2019-11-28 12:43:43,902 INFO L92 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat Starting monitored process 13 with mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with mathsat -unsat_core_generation=3 [2019-11-28 12:43:44,123 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2019-11-28 12:43:44,123 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2019-11-28 12:43:44,144 INFO L255 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 72 conjunts are in the unsatisfiable core [2019-11-28 12:43:44,146 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2019-11-28 12:43:44,223 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:43:44,372 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2019-11-28 12:43:44,373 INFO L508 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2019-11-28 12:43:44,392 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:43:44,392 INFO L508 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:43:44,393 INFO L221 ElimStorePlain]: Needed 2 recursive calls to eliminate 1 variables, input treesize:39, output treesize:35 [2019-11-28 12:43:46,685 WARN L192 SmtUtils]: Spent 370.00 ms on a formula simplification that was a NOOP. DAG size: 39 [2019-11-28 12:43:48,699 WARN L860 $PredicateComparison]: unable to prove that (exists ((downsweep_~tmp~0 (_ BitVec 32))) (= |c_#memory_int| (store |c_old(#memory_int)| |c_downsweep_#in~a.base| (let ((.cse2 (bvadd (bvmul |c_downsweep_#in~left| (_ bv4 32)) |c_downsweep_#in~a.offset|))) (store (let ((.cse0 (select |c_old(#memory_int)| |c_downsweep_#in~a.base|)) (.cse1 (bvadd |c_downsweep_#in~a.offset| (bvmul |c_downsweep_#in~right| (_ bv4 32))))) (store .cse0 .cse1 (bvadd (select .cse0 .cse2) (select .cse0 .cse1)))) .cse2 downsweep_~tmp~0))))) is different from true [2019-11-28 12:43:50,785 WARN L860 $PredicateComparison]: unable to prove that (exists ((downsweep_~tmp~0 (_ BitVec 32))) (= (store |c_old(#memory_int)| |c_downsweep_#in~a.base| (let ((.cse9 (bvmul (bvneg (bvsdiv (bvadd (bvneg |c_downsweep_#in~left|) |c_downsweep_#in~right|) (_ bv2 32))) (_ bv4 32))) (.cse10 (bvmul |c_downsweep_#in~right| (_ bv4 32)))) (let ((.cse2 (bvadd .cse9 |c_downsweep_#in~a.offset| .cse10))) (store (let ((.cse1 (bvadd |c_downsweep_#in~a.offset| .cse10))) (let ((.cse0 (let ((.cse7 (select |c_old(#memory_int)| |c_downsweep_#in~a.base|)) (.cse8 (bvmul |c_downsweep_#in~left| (_ bv4 32)))) (let ((.cse6 (bvadd .cse9 .cse8 |c_downsweep_#in~a.offset|)) (.cse5 (select .cse7 .cse1))) (store (let ((.cse4 (bvadd .cse8 |c_downsweep_#in~a.offset|))) (let ((.cse3 (store .cse7 .cse1 (bvadd (select .cse7 .cse4) .cse5)))) (store .cse3 .cse4 (bvadd (select (store .cse3 .cse4 .cse5) .cse6) .cse5)))) .cse6 .cse5))))) (store .cse0 .cse1 (bvadd (select .cse0 .cse1) (select .cse0 .cse2))))) .cse2 downsweep_~tmp~0)))) |c_#memory_int|)) is different from true [2019-11-28 12:43:50,799 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 559 treesize of output 502 [2019-11-28 12:43:50,823 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:50,863 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:50,902 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:50,941 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:50,981 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,001 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,043 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,082 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,103 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,125 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,164 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,205 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,228 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,267 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,306 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,346 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,391 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,412 INFO L189 IndexEqualityManager]: detected not equals via solver [2019-11-28 12:43:51,413 INFO L237 Elim1Store]: Index analysis took 205 ms [2019-11-28 12:43:51,415 INFO L377 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 185 treesize of output 89 [2019-11-28 12:43:51,415 INFO L508 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2019-11-28 12:43:51,710 WARN L192 SmtUtils]: Spent 294.00 ms on a formula simplification that was a NOOP. DAG size: 27 [2019-11-28 12:43:51,710 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:43:51,711 INFO L508 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2019-11-28 12:43:52,064 WARN L192 SmtUtils]: Spent 352.00 ms on a formula simplification that was a NOOP. DAG size: 36 [2019-11-28 12:43:52,064 INFO L588 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2019-11-28 12:43:52,065 INFO L508 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2019-11-28 12:43:52,065 INFO L221 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:581, output treesize:51 [2019-11-28 12:43:52,951 WARN L192 SmtUtils]: Spent 132.00 ms on a formula simplification that was a NOOP. DAG size: 33 [2019-11-28 12:43:54,225 WARN L192 SmtUtils]: Spent 219.00 ms on a formula simplification that was a NOOP. DAG size: 37 [2019-11-28 12:43:54,227 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:43:54,551 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 32 trivial. 8 not checked. [2019-11-28 12:43:54,551 INFO L320 TraceCheckSpWp]: Computing backward predicates... [2019-11-28 12:43:56,005 WARN L192 SmtUtils]: Spent 563.00 ms on a formula simplification that was a NOOP. DAG size: 46 [2019-11-28 12:43:56,502 WARN L192 SmtUtils]: Spent 496.00 ms on a formula simplification that was a NOOP. DAG size: 44 [2019-11-28 12:43:57,008 WARN L192 SmtUtils]: Spent 406.00 ms on a formula simplification that was a NOOP. DAG size: 45 [2019-11-28 12:43:57,407 WARN L192 SmtUtils]: Spent 399.00 ms on a formula simplification that was a NOOP. DAG size: 43 [2019-11-28 12:43:59,970 WARN L192 SmtUtils]: Spent 2.56 s on a formula simplification that was a NOOP. DAG size: 104 [2019-11-28 12:44:00,801 WARN L192 SmtUtils]: Spent 828.00 ms on a formula simplification that was a NOOP. DAG size: 50 [2019-11-28 12:44:02,436 WARN L192 SmtUtils]: Spent 1.63 s on a formula simplification that was a NOOP. DAG size: 65 [2019-11-28 12:44:04,089 WARN L192 SmtUtils]: Spent 1.65 s on a formula simplification that was a NOOP. DAG size: 63 [2019-11-28 12:44:13,833 WARN L192 SmtUtils]: Spent 414.00 ms on a formula simplification that was a NOOP. DAG size: 57 [2019-11-28 12:44:14,465 WARN L192 SmtUtils]: Spent 498.00 ms on a formula simplification that was a NOOP. DAG size: 45 [2019-11-28 12:44:14,923 WARN L192 SmtUtils]: Spent 457.00 ms on a formula simplification that was a NOOP. DAG size: 43 [2019-11-28 12:44:24,404 WARN L192 SmtUtils]: Spent 900.00 ms on a formula simplification that was a NOOP. DAG size: 76 [2019-11-28 12:44:24,407 INFO L319 QuantifierPusher]: Applying distributivity, recursing on 2 terms [2019-11-28 12:44:24,614 WARN L499 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 mathsat -unsat_core_generation=3 [2019-11-28 12:44:24,616 FATAL L? ?]: The Plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction has thrown an exception: java.lang.AssertionError: Alternating quantifiers not yet supported at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.ElimStorePlain.applyComplexEliminationRules(ElimStorePlain.java:283) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.ElimStorePlain.doElimOneRec(ElimStorePlain.java:264) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.ElimStorePlain.eliminateOne(ElimStorePlain.java:565) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.ElimStorePlain.doElimAllRec(ElimStorePlain.java:478) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.ElimStorePlain.startRecursiveElimination(ElimStorePlain.java:216) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.PartialQuantifierElimination.elim(PartialQuantifierElimination.java:306) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.PartialQuantifierElimination.tryToEliminate(PartialQuantifierElimination.java:102) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer$QuantifierEliminationPostprocessor.postprocess(IterativePredicateTransformer.java:246) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.applyPostprocessors(IterativePredicateTransformer.java:440) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.computeBackwardSequence(IterativePredicateTransformer.java:419) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.computeWeakestPreconditionSequence(IterativePredicateTransformer.java:291) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.computeInterpolantsUsingUnsatCore(TraceCheckSpWp.java:334) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.computeInterpolants(TraceCheckSpWp.java:177) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.(TraceCheckSpWp.java:162) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSpWp.construct(IpTcStrategyModuleSpWp.java:108) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSpWp.construct(IpTcStrategyModuleSpWp.java:1) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.isCorrect(IpTcStrategyModuleBase.java:57) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.checkFeasibility(AutomatonFreeRefinementEngine.java:242) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:166) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:75) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:463) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterateInternal(AbstractCegarLoop.java:419) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:368) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.CegarLoopResult.iterate(CegarLoopResult.java:139) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.iterateNew(TraceAbstractionStarter.java:332) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:174) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:126) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:120) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:168) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:151) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:128) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:232) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:226) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:142) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:104) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:316) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:55) [2019-11-28 12:44:24,632 INFO L168 Benchmark]: Toolchain (without parser) took 843708.53 ms. Allocated memory was 1.0 GB in the beginning and 1.2 GB in the end (delta: 210.2 MB). Free memory was 960.4 MB in the beginning and 1.1 GB in the end (delta: -119.0 MB). Peak memory consumption was 91.2 MB. Max. memory is 11.5 GB. [2019-11-28 12:44:24,632 INFO L168 Benchmark]: CDTParser took 0.31 ms. Allocated memory is still 1.0 GB. Free memory is still 987.2 MB. There was no memory consumed. Max. memory is 11.5 GB. [2019-11-28 12:44:24,633 INFO L168 Benchmark]: CACSL2BoogieTranslator took 426.81 ms. Allocated memory was 1.0 GB in the beginning and 1.1 GB in the end (delta: 120.1 MB). Free memory was 960.4 MB in the beginning and 1.1 GB in the end (delta: -149.4 MB). Peak memory consumption was 20.4 MB. Max. memory is 11.5 GB. [2019-11-28 12:44:24,633 INFO L168 Benchmark]: Boogie Procedure Inliner took 47.27 ms. Allocated memory is still 1.1 GB. Free memory is still 1.1 GB. There was no memory consumed. Max. memory is 11.5 GB. [2019-11-28 12:44:24,634 INFO L168 Benchmark]: Boogie Preprocessor took 34.72 ms. Allocated memory is still 1.1 GB. Free memory is still 1.1 GB. There was no memory consumed. Max. memory is 11.5 GB. [2019-11-28 12:44:24,635 INFO L168 Benchmark]: RCFGBuilder took 475.38 ms. Allocated memory is still 1.1 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 25.6 MB). Peak memory consumption was 25.6 MB. Max. memory is 11.5 GB. [2019-11-28 12:44:24,636 INFO L168 Benchmark]: TraceAbstraction took 842719.03 ms. Allocated memory was 1.1 GB in the beginning and 1.2 GB in the end (delta: 90.2 MB). Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 4.8 MB). Peak memory consumption was 95.0 MB. Max. memory is 11.5 GB. [2019-11-28 12:44:24,646 INFO L335 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.31 ms. Allocated memory is still 1.0 GB. Free memory is still 987.2 MB. There was no memory consumed. Max. memory is 11.5 GB. * CACSL2BoogieTranslator took 426.81 ms. Allocated memory was 1.0 GB in the beginning and 1.1 GB in the end (delta: 120.1 MB). Free memory was 960.4 MB in the beginning and 1.1 GB in the end (delta: -149.4 MB). Peak memory consumption was 20.4 MB. Max. memory is 11.5 GB. * Boogie Procedure Inliner took 47.27 ms. Allocated memory is still 1.1 GB. Free memory is still 1.1 GB. There was no memory consumed. Max. memory is 11.5 GB. * Boogie Preprocessor took 34.72 ms. Allocated memory is still 1.1 GB. Free memory is still 1.1 GB. There was no memory consumed. Max. memory is 11.5 GB. * RCFGBuilder took 475.38 ms. Allocated memory is still 1.1 GB. Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 25.6 MB). Peak memory consumption was 25.6 MB. Max. memory is 11.5 GB. * TraceAbstraction took 842719.03 ms. Allocated memory was 1.1 GB in the beginning and 1.2 GB in the end (delta: 90.2 MB). Free memory was 1.1 GB in the beginning and 1.1 GB in the end (delta: 4.8 MB). Peak memory consumption was 95.0 MB. Max. memory is 11.5 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - ExceptionOrErrorResult: AssertionError: Alternating quantifiers not yet supported de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: AssertionError: Alternating quantifiers not yet supported: de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.ElimStorePlain.applyComplexEliminationRules(ElimStorePlain.java:283) RESULT: Ultimate could not prove your program: Toolchain returned no result. Received shutdown request...