./Ultimate.py --spec ../../../trunk/examples/svcomp/ReachSafety.prp --file ../../../trunk/examples/svcomp/loop-acceleration/phases_true-unreach-call2_false-termination.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8c3fbe1c Calling Ultimate with: java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/config -Xmx12G -Xms1G -jar /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/config/TaipanReach.xml -i ../../../trunk/examples/svcomp/loop-acceleration/phases_true-unreach-call2_false-termination.i -s /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UTaipan-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 Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 4a156731963582ce9a466285688eba3a68b58029 ........................................................................................................................................................................................................................................................................................................................................................................................................................................................... Execution finished normally Writing output log to file Ultimate.log Result: TRUE --- Real Ultimate output --- This is Ultimate 0.1.23-8c3fbe1 [2018-10-22 15:06:43,438 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-22 15:06:43,439 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-22 15:06:43,451 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-22 15:06:43,451 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-22 15:06:43,452 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-22 15:06:43,453 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-22 15:06:43,456 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-22 15:06:43,459 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-22 15:06:43,460 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-22 15:06:43,461 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-22 15:06:43,461 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-22 15:06:43,462 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-22 15:06:43,463 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-22 15:06:43,464 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-22 15:06:43,465 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-22 15:06:43,465 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-22 15:06:43,467 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-22 15:06:43,469 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-22 15:06:43,470 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-22 15:06:43,471 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-22 15:06:43,473 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-22 15:06:43,475 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-22 15:06:43,475 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-22 15:06:43,475 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-22 15:06:43,476 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-22 15:06:43,477 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-22 15:06:43,478 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-22 15:06:43,479 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-22 15:06:43,480 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-22 15:06:43,480 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-22 15:06:43,481 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-22 15:06:43,481 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-22 15:06:43,481 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-22 15:06:43,482 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-22 15:06:43,483 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-22 15:06:43,484 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/config/svcomp-Reach-32bit-Taipan_Default.epf [2018-10-22 15:06:43,501 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-22 15:06:43,507 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-22 15:06:43,508 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-10-22 15:06:43,508 INFO L133 SettingsManager]: * User list type=DISABLED [2018-10-22 15:06:43,509 INFO L133 SettingsManager]: * calls to implemented procedures=false [2018-10-22 15:06:43,511 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-22 15:06:43,511 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2018-10-22 15:06:43,511 INFO L133 SettingsManager]: * Abstract domain=CompoundDomain [2018-10-22 15:06:43,512 INFO L133 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2018-10-22 15:06:43,512 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-22 15:06:43,512 INFO L133 SettingsManager]: * Interval Domain=false [2018-10-22 15:06:43,513 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-10-22 15:06:43,513 INFO L133 SettingsManager]: * sizeof long=4 [2018-10-22 15:06:43,513 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-10-22 15:06:43,513 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-10-22 15:06:43,513 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-10-22 15:06:43,514 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-10-22 15:06:43,516 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-10-22 15:06:43,516 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-10-22 15:06:43,516 INFO L133 SettingsManager]: * sizeof long double=12 [2018-10-22 15:06:43,517 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-10-22 15:06:43,517 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-10-22 15:06:43,517 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-22 15:06:43,517 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-10-22 15:06:43,517 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-10-22 15:06:43,517 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-10-22 15:06:43,518 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-22 15:06:43,518 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-22 15:06:43,518 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-10-22 15:06:43,518 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-10-22 15:06:43,518 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-10-22 15:06:43,518 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-10-22 15:06:43,521 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-22 15:06:43,522 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-10-22 15:06:43,523 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES 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/UTaipan-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 -> Taipan 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 -> 4a156731963582ce9a466285688eba3a68b58029 [2018-10-22 15:06:43,606 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-22 15:06:43,621 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-22 15:06:43,625 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-22 15:06:43,626 INFO L271 PluginConnector]: Initializing CDTParser... [2018-10-22 15:06:43,626 INFO L276 PluginConnector]: CDTParser initialized [2018-10-22 15:06:43,627 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/../../../trunk/examples/svcomp/loop-acceleration/phases_true-unreach-call2_false-termination.i [2018-10-22 15:06:43,683 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/1c570ad0e/1c71f8136af04bb8a985ea8c3af3ea8f/FLAG209fae6f3 [2018-10-22 15:06:44,085 INFO L298 CDTParser]: Found 1 translation units. [2018-10-22 15:06:44,085 INFO L158 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/loop-acceleration/phases_true-unreach-call2_false-termination.i [2018-10-22 15:06:44,092 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/1c570ad0e/1c71f8136af04bb8a985ea8c3af3ea8f/FLAG209fae6f3 [2018-10-22 15:06:44,107 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/1c570ad0e/1c71f8136af04bb8a985ea8c3af3ea8f [2018-10-22 15:06:44,113 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-22 15:06:44,114 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2018-10-22 15:06:44,115 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-10-22 15:06:44,115 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-10-22 15:06:44,119 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-10-22 15:06:44,120 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.10 03:06:44" (1/1) ... [2018-10-22 15:06:44,123 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@10a2fbe9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:06:44, skipping insertion in model container [2018-10-22 15:06:44,123 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.10 03:06:44" (1/1) ... [2018-10-22 15:06:44,133 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-10-22 15:06:44,153 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-10-22 15:06:44,327 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-10-22 15:06:44,330 INFO L189 MainTranslator]: Completed pre-run [2018-10-22 15:06:44,350 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-10-22 15:06:44,363 INFO L193 MainTranslator]: Completed translation [2018-10-22 15:06:44,364 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:06:44 WrapperNode [2018-10-22 15:06:44,364 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-10-22 15:06:44,364 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-10-22 15:06:44,365 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-10-22 15:06:44,365 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-10-22 15:06:44,372 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:06:44" (1/1) ... [2018-10-22 15:06:44,376 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:06:44" (1/1) ... [2018-10-22 15:06:44,382 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-10-22 15:06:44,382 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-22 15:06:44,382 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-22 15:06:44,383 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-22 15:06:44,392 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:06:44" (1/1) ... [2018-10-22 15:06:44,392 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:06:44" (1/1) ... [2018-10-22 15:06:44,393 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:06:44" (1/1) ... [2018-10-22 15:06:44,393 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:06:44" (1/1) ... [2018-10-22 15:06:44,396 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:06:44" (1/1) ... [2018-10-22 15:06:44,401 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:06:44" (1/1) ... [2018-10-22 15:06:44,402 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:06:44" (1/1) ... [2018-10-22 15:06:44,403 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-22 15:06:44,403 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-22 15:06:44,404 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-22 15:06:44,404 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-22 15:06:44,405 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:06:44" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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 [2018-10-22 15:06:44,529 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-10-22 15:06:44,529 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-10-22 15:06:44,529 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-22 15:06:44,529 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-22 15:06:44,529 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-10-22 15:06:44,529 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-10-22 15:06:44,530 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2018-10-22 15:06:44,530 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2018-10-22 15:06:44,768 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-22 15:06:44,769 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.10 03:06:44 BoogieIcfgContainer [2018-10-22 15:06:44,769 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-22 15:06:44,771 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-22 15:06:44,771 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-22 15:06:44,775 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-22 15:06:44,775 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 22.10 03:06:44" (1/3) ... [2018-10-22 15:06:44,776 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4f43fc16 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.10 03:06:44, skipping insertion in model container [2018-10-22 15:06:44,777 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:06:44" (2/3) ... [2018-10-22 15:06:44,777 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4f43fc16 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.10 03:06:44, skipping insertion in model container [2018-10-22 15:06:44,777 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.10 03:06:44" (3/3) ... [2018-10-22 15:06:44,781 INFO L112 eAbstractionObserver]: Analyzing ICFG phases_true-unreach-call2_false-termination.i [2018-10-22 15:06:44,815 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-10-22 15:06:44,833 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-22 15:06:44,869 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-22 15:06:44,923 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-22 15:06:44,924 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-22 15:06:44,924 INFO L383 AbstractCegarLoop]: Hoare is true [2018-10-22 15:06:44,924 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-10-22 15:06:44,924 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-22 15:06:44,924 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-22 15:06:44,924 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-22 15:06:44,925 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-22 15:06:44,925 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-22 15:06:44,939 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states. [2018-10-22 15:06:44,945 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-10-22 15:06:44,946 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:06:44,946 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:06:44,950 INFO L424 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:06:44,955 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:06:44,955 INFO L82 PathProgramCache]: Analyzing trace with hash -1994259344, now seen corresponding path program 1 times [2018-10-22 15:06:44,957 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:06:45,002 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:06:45,002 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:06:45,002 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:06:45,003 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:06:45,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:06:45,061 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:06:45,063 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-22 15:06:45,063 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-10-22 15:06:45,063 INFO L265 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-22 15:06:45,067 INFO L460 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-10-22 15:06:45,079 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-10-22 15:06:45,080 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-10-22 15:06:45,083 INFO L87 Difference]: Start difference. First operand 20 states. Second operand 2 states. [2018-10-22 15:06:45,103 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:06:45,103 INFO L93 Difference]: Finished difference Result 31 states and 36 transitions. [2018-10-22 15:06:45,103 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-10-22 15:06:45,105 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 11 [2018-10-22 15:06:45,105 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:06:45,112 INFO L225 Difference]: With dead ends: 31 [2018-10-22 15:06:45,113 INFO L226 Difference]: Without dead ends: 14 [2018-10-22 15:06:45,116 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-10-22 15:06:45,130 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14 states. [2018-10-22 15:06:45,147 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-10-22 15:06:45,149 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14 states. [2018-10-22 15:06:45,149 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 15 transitions. [2018-10-22 15:06:45,151 INFO L78 Accepts]: Start accepts. Automaton has 14 states and 15 transitions. Word has length 11 [2018-10-22 15:06:45,151 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:06:45,152 INFO L481 AbstractCegarLoop]: Abstraction has 14 states and 15 transitions. [2018-10-22 15:06:45,152 INFO L482 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-10-22 15:06:45,152 INFO L276 IsEmpty]: Start isEmpty. Operand 14 states and 15 transitions. [2018-10-22 15:06:45,152 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2018-10-22 15:06:45,153 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:06:45,153 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:06:45,153 INFO L424 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:06:45,153 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:06:45,154 INFO L82 PathProgramCache]: Analyzing trace with hash -2119643788, now seen corresponding path program 1 times [2018-10-22 15:06:45,154 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:06:45,155 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:06:45,155 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:06:45,155 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:06:45,155 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:06:45,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:06:45,354 WARN L179 SmtUtils]: Spent 100.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-10-22 15:06:45,636 WARN L179 SmtUtils]: Spent 132.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 17 [2018-10-22 15:06:45,710 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:06:45,711 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-22 15:06:45,711 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-10-22 15:06:45,711 INFO L265 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-22 15:06:45,713 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-10-22 15:06:45,713 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-10-22 15:06:45,713 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-10-22 15:06:45,714 INFO L87 Difference]: Start difference. First operand 14 states and 15 transitions. Second operand 7 states. [2018-10-22 15:06:45,991 WARN L179 SmtUtils]: Spent 180.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 15 [2018-10-22 15:06:46,200 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:06:46,201 INFO L93 Difference]: Finished difference Result 22 states and 24 transitions. [2018-10-22 15:06:46,201 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-10-22 15:06:46,201 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 12 [2018-10-22 15:06:46,201 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:06:46,202 INFO L225 Difference]: With dead ends: 22 [2018-10-22 15:06:46,202 INFO L226 Difference]: Without dead ends: 17 [2018-10-22 15:06:46,203 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=25, Invalid=65, Unknown=0, NotChecked=0, Total=90 [2018-10-22 15:06:46,204 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2018-10-22 15:06:46,207 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-10-22 15:06:46,209 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 17 states. [2018-10-22 15:06:46,210 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 19 transitions. [2018-10-22 15:06:46,210 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 19 transitions. Word has length 12 [2018-10-22 15:06:46,210 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:06:46,210 INFO L481 AbstractCegarLoop]: Abstraction has 17 states and 19 transitions. [2018-10-22 15:06:46,210 INFO L482 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-10-22 15:06:46,211 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 19 transitions. [2018-10-22 15:06:46,212 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-10-22 15:06:46,212 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:06:46,212 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:06:46,213 INFO L424 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:06:46,213 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:06:46,213 INFO L82 PathProgramCache]: Analyzing trace with hash -1089190421, now seen corresponding path program 1 times [2018-10-22 15:06:46,214 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:06:46,215 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:06:46,215 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:06:46,215 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:06:46,216 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:06:46,222 ERROR L235 seRefinementStrategy]: Caught known exception: Unsupported non-linear arithmetic [2018-10-22 15:06:46,222 INFO L258 seRefinementStrategy]: Advancing trace checker [2018-10-22 15:06:46,223 INFO L174 anRefinementStrategy]: Switched to traceCheck mode Z3_NO_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2018-10-22 15:06:46,240 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:06:46,240 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_NO_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: null) [2018-10-22 15:06:46,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:06:46,268 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 16 with the following transitions: [2018-10-22 15:06:46,270 INFO L202 CegarAbsIntRunner]: [0], [4], [8], [12], [16], [18], [23], [30], [33], [35], [41], [42], [43], [45] [2018-10-22 15:06:46,314 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-10-22 15:06:46,315 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-10-22 15:06:46,439 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-10-22 15:06:46,823 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-10-22 15:06:46,825 INFO L272 AbstractInterpreter]: Visited 14 different actions 70 times. Merged at 4 different actions 28 times. Widened at 1 different actions 3 times. Found 1 fixpoints after 1 different actions. Largest state had 4 variables. [2018-10-22 15:06:46,874 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:06:46,875 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-10-22 15:06:46,875 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:06:46,876 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-22 15:06:46,891 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:06:46,891 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-22 15:06:46,920 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:06:46,928 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:06:47,127 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:06:47,127 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:06:47,472 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:06:47,492 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-10-22 15:06:47,492 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [8] total 13 [2018-10-22 15:06:47,493 INFO L265 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-22 15:06:47,493 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-10-22 15:06:47,493 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-10-22 15:06:47,494 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2018-10-22 15:06:47,494 INFO L87 Difference]: Start difference. First operand 17 states and 19 transitions. Second operand 7 states. [2018-10-22 15:06:51,716 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:06:51,717 INFO L93 Difference]: Finished difference Result 24 states and 26 transitions. [2018-10-22 15:06:51,719 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-10-22 15:06:51,719 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 15 [2018-10-22 15:06:51,719 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:06:51,720 INFO L225 Difference]: With dead ends: 24 [2018-10-22 15:06:51,720 INFO L226 Difference]: Without dead ends: 19 [2018-10-22 15:06:51,720 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=42, Invalid=168, Unknown=0, NotChecked=0, Total=210 [2018-10-22 15:06:51,721 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2018-10-22 15:06:51,724 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-10-22 15:06:51,724 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19 states. [2018-10-22 15:06:51,725 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 21 transitions. [2018-10-22 15:06:51,725 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 21 transitions. Word has length 15 [2018-10-22 15:06:51,725 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:06:51,725 INFO L481 AbstractCegarLoop]: Abstraction has 19 states and 21 transitions. [2018-10-22 15:06:51,726 INFO L482 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-10-22 15:06:51,726 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 21 transitions. [2018-10-22 15:06:51,726 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2018-10-22 15:06:51,726 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:06:51,727 INFO L375 BasicCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:06:51,727 INFO L424 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:06:51,727 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:06:51,727 INFO L82 PathProgramCache]: Analyzing trace with hash -759205998, now seen corresponding path program 1 times [2018-10-22 15:06:51,727 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:06:51,728 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:06:51,728 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:06:51,729 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:06:51,729 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:06:51,733 ERROR L235 seRefinementStrategy]: Caught known exception: Unsupported non-linear arithmetic [2018-10-22 15:06:51,733 INFO L258 seRefinementStrategy]: Advancing trace checker [2018-10-22 15:06:51,733 INFO L174 anRefinementStrategy]: Switched to traceCheck mode Z3_NO_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2018-10-22 15:06:51,752 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:06:51,752 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_NO_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: null) [2018-10-22 15:06:51,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:06:51,807 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 19 with the following transitions: [2018-10-22 15:06:51,807 INFO L202 CegarAbsIntRunner]: [0], [4], [8], [12], [16], [18], [21], [23], [30], [33], [35], [41], [42], [43], [45] [2018-10-22 15:06:51,812 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-10-22 15:06:51,812 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-10-22 15:06:51,825 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-10-22 15:06:52,199 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-10-22 15:06:52,199 INFO L272 AbstractInterpreter]: Visited 15 different actions 78 times. Merged at 5 different actions 28 times. Widened at 1 different actions 2 times. Found 9 fixpoints after 2 different actions. Largest state had 4 variables. [2018-10-22 15:06:52,241 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:06:52,242 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-10-22 15:06:52,242 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:06:52,242 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-22 15:06:52,258 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:06:52,258 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-22 15:06:52,272 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:06:52,274 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:06:52,345 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-10-22 15:06:52,346 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:06:54,434 WARN L854 $PredicateComparison]: unable to prove that (let ((.cse0 (mod (* c_main_~x~0 c_main_~x~0) 4294967296)) (.cse1 (mod c_main_~y~0 4294967296))) (or (< .cse0 .cse1) (= .cse1 .cse0) (let ((.cse9 (mod c_main_~x~0 4294967296))) (let ((.cse8 (div .cse1 .cse9))) (let ((.cse6 (= (mod .cse1 .cse9) 0)) (.cse12 (<= (mod .cse8 4294967296) .cse9)) (.cse13 (<= 0 .cse9))) (let ((.cse5 (<= 0 .cse1)) (.cse7 (or (<= (mod (+ .cse8 4294967295) 4294967296) .cse9) .cse13)) (.cse3 (or .cse12 .cse13)) (.cse10 (< .cse9 0)) (.cse2 (and (not .cse6) (< .cse1 0)))) (and (or (let ((.cse4 (or (<= (mod (+ .cse8 1) 4294967296) .cse9) .cse10))) (and (or .cse2 (and .cse3 .cse4)) (or .cse5 .cse6 (and .cse7 .cse4)))) .cse5 .cse6) (or (let ((.cse11 (or .cse12 .cse10))) (and (or .cse5 .cse6 (and .cse7 .cse11)) (or .cse2 (and .cse3 .cse11)))) .cse2)))))))) is different from true [2018-10-22 15:06:54,838 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-10-22 15:06:54,858 INFO L312 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-10-22 15:06:54,859 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4, 7] imperfect sequences [] total 9 [2018-10-22 15:06:54,859 INFO L265 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-22 15:06:54,859 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-22 15:06:54,860 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-22 15:06:54,861 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=41, Unknown=1, NotChecked=12, Total=72 [2018-10-22 15:06:54,862 INFO L87 Difference]: Start difference. First operand 19 states and 21 transitions. Second operand 4 states. [2018-10-22 15:06:54,888 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:06:54,889 INFO L93 Difference]: Finished difference Result 21 states and 23 transitions. [2018-10-22 15:06:54,890 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-22 15:06:54,890 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 18 [2018-10-22 15:06:54,890 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:06:54,890 INFO L225 Difference]: With dead ends: 21 [2018-10-22 15:06:54,890 INFO L226 Difference]: Without dead ends: 0 [2018-10-22 15:06:54,891 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 26 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=18, Invalid=41, Unknown=1, NotChecked=12, Total=72 [2018-10-22 15:06:54,891 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2018-10-22 15:06:54,891 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2018-10-22 15:06:54,892 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 0 states. [2018-10-22 15:06:54,892 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2018-10-22 15:06:54,892 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 18 [2018-10-22 15:06:54,892 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:06:54,892 INFO L481 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2018-10-22 15:06:54,892 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-22 15:06:54,892 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2018-10-22 15:06:54,893 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-10-22 15:06:54,897 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2018-10-22 15:06:55,012 INFO L428 ceAbstractionStarter]: At program point ULTIMATE.initFINAL(line -1) the Hoare annotation is: true [2018-10-22 15:06:55,012 INFO L425 ceAbstractionStarter]: For program point ULTIMATE.initEXIT(line -1) no Hoare annotation was computed. [2018-10-22 15:06:55,012 INFO L425 ceAbstractionStarter]: For program point ULTIMATE.startEXIT(line -1) no Hoare annotation was computed. [2018-10-22 15:06:55,012 INFO L428 ceAbstractionStarter]: At program point L-1(line -1) the Hoare annotation is: true [2018-10-22 15:06:55,012 INFO L428 ceAbstractionStarter]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2018-10-22 15:06:55,013 INFO L425 ceAbstractionStarter]: For program point ULTIMATE.startFINAL(line -1) no Hoare annotation was computed. [2018-10-22 15:06:55,013 INFO L428 ceAbstractionStarter]: At program point mainENTRY(lines 10 22) the Hoare annotation is: true [2018-10-22 15:06:55,013 INFO L425 ceAbstractionStarter]: For program point mainEXIT(lines 10 22) no Hoare annotation was computed. [2018-10-22 15:06:55,013 INFO L425 ceAbstractionStarter]: For program point L15(lines 15 19) no Hoare annotation was computed. [2018-10-22 15:06:55,013 INFO L425 ceAbstractionStarter]: For program point L13(line 13) no Hoare annotation was computed. [2018-10-22 15:06:55,013 INFO L425 ceAbstractionStarter]: For program point L14-1(lines 14 20) no Hoare annotation was computed. [2018-10-22 15:06:55,014 INFO L421 ceAbstractionStarter]: At program point L15-2(lines 14 20) the Hoare annotation is: (and (<= main_~x~0 1) (<= 1 main_~x~0) (<= (+ (* 4294967296 (div main_~y~0 4294967296)) main_~x~0) main_~y~0)) [2018-10-22 15:06:55,014 INFO L425 ceAbstractionStarter]: For program point mainFINAL(lines 10 22) no Hoare annotation was computed. [2018-10-22 15:06:55,014 INFO L421 ceAbstractionStarter]: At program point L14-3(lines 14 20) the Hoare annotation is: (= (mod main_~y~0 4294967296) (mod main_~x~0 4294967296)) [2018-10-22 15:06:55,014 INFO L428 ceAbstractionStarter]: At program point __VERIFIER_assertENTRY(lines 4 9) the Hoare annotation is: true [2018-10-22 15:06:55,014 INFO L425 ceAbstractionStarter]: For program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 6) no Hoare annotation was computed. [2018-10-22 15:06:55,014 INFO L425 ceAbstractionStarter]: For program point __VERIFIER_assertEXIT(lines 4 9) no Hoare annotation was computed. [2018-10-22 15:06:55,014 INFO L425 ceAbstractionStarter]: For program point L6(line 6) no Hoare annotation was computed. [2018-10-22 15:06:55,015 INFO L425 ceAbstractionStarter]: For program point L5(lines 5 7) no Hoare annotation was computed. [2018-10-22 15:06:55,015 INFO L425 ceAbstractionStarter]: For program point L5-2(lines 4 9) no Hoare annotation was computed. [2018-10-22 15:06:55,026 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.10 03:06:55 BoogieIcfgContainer [2018-10-22 15:06:55,026 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-10-22 15:06:55,027 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2018-10-22 15:06:55,027 INFO L271 PluginConnector]: Initializing Witness Printer... [2018-10-22 15:06:55,027 INFO L276 PluginConnector]: Witness Printer initialized [2018-10-22 15:06:55,028 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.10 03:06:44" (3/4) ... [2018-10-22 15:06:55,031 INFO L144 WitnessPrinter]: Generating witness for correct program [2018-10-22 15:06:55,035 INFO L333 RCFGBacktranslator]: Ignoring RootEdge to procedure ULTIMATE.init [2018-10-22 15:06:55,036 INFO L333 RCFGBacktranslator]: Ignoring RootEdge to procedure main [2018-10-22 15:06:55,036 INFO L333 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2018-10-22 15:06:55,039 INFO L846 BoogieBacktranslator]: Reduced CFG by removing 9 nodes and edges [2018-10-22 15:06:55,039 INFO L846 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2018-10-22 15:06:55,039 INFO L846 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2018-10-22 15:06:55,083 INFO L145 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/witness.graphml [2018-10-22 15:06:55,083 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2018-10-22 15:06:55,084 INFO L168 Benchmark]: Toolchain (without parser) took 10970.82 ms. Allocated memory was 1.0 GB in the beginning and 1.1 GB in the end (delta: 118.5 MB). Free memory was 954.5 MB in the beginning and 910.7 MB in the end (delta: 43.8 MB). Peak memory consumption was 162.3 MB. Max. memory is 11.5 GB. [2018-10-22 15:06:55,088 INFO L168 Benchmark]: CDTParser took 0.21 ms. Allocated memory is still 1.0 GB. Free memory is still 978.7 MB. There was no memory consumed. Max. memory is 11.5 GB. [2018-10-22 15:06:55,089 INFO L168 Benchmark]: CACSL2BoogieTranslator took 248.81 ms. Allocated memory is still 1.0 GB. Free memory was 954.5 MB in the beginning and 943.8 MB in the end (delta: 10.7 MB). Peak memory consumption was 10.7 MB. Max. memory is 11.5 GB. [2018-10-22 15:06:55,090 INFO L168 Benchmark]: Boogie Procedure Inliner took 17.71 ms. Allocated memory is still 1.0 GB. Free memory is still 943.8 MB. There was no memory consumed. Max. memory is 11.5 GB. [2018-10-22 15:06:55,093 INFO L168 Benchmark]: Boogie Preprocessor took 20.79 ms. Allocated memory is still 1.0 GB. Free memory is still 943.8 MB. There was no memory consumed. Max. memory is 11.5 GB. [2018-10-22 15:06:55,094 INFO L168 Benchmark]: RCFGBuilder took 366.08 ms. Allocated memory was 1.0 GB in the beginning and 1.1 GB in the end (delta: 118.5 MB). Free memory was 943.8 MB in the beginning and 1.1 GB in the end (delta: -158.3 MB). Peak memory consumption was 26.4 MB. Max. memory is 11.5 GB. [2018-10-22 15:06:55,095 INFO L168 Benchmark]: TraceAbstraction took 10255.16 ms. Allocated memory is still 1.1 GB. Free memory was 1.1 GB in the beginning and 910.7 MB in the end (delta: 184.4 MB). Peak memory consumption was 184.4 MB. Max. memory is 11.5 GB. [2018-10-22 15:06:55,095 INFO L168 Benchmark]: Witness Printer took 56.72 ms. Allocated memory is still 1.1 GB. Free memory is still 910.7 MB. There was no memory consumed. Max. memory is 11.5 GB. [2018-10-22 15:06:55,100 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.21 ms. Allocated memory is still 1.0 GB. Free memory is still 978.7 MB. There was no memory consumed. Max. memory is 11.5 GB. * CACSL2BoogieTranslator took 248.81 ms. Allocated memory is still 1.0 GB. Free memory was 954.5 MB in the beginning and 943.8 MB in the end (delta: 10.7 MB). Peak memory consumption was 10.7 MB. Max. memory is 11.5 GB. * Boogie Procedure Inliner took 17.71 ms. Allocated memory is still 1.0 GB. Free memory is still 943.8 MB. There was no memory consumed. Max. memory is 11.5 GB. * Boogie Preprocessor took 20.79 ms. Allocated memory is still 1.0 GB. Free memory is still 943.8 MB. There was no memory consumed. Max. memory is 11.5 GB. * RCFGBuilder took 366.08 ms. Allocated memory was 1.0 GB in the beginning and 1.1 GB in the end (delta: 118.5 MB). Free memory was 943.8 MB in the beginning and 1.1 GB in the end (delta: -158.3 MB). Peak memory consumption was 26.4 MB. Max. memory is 11.5 GB. * TraceAbstraction took 10255.16 ms. Allocated memory is still 1.1 GB. Free memory was 1.1 GB in the beginning and 910.7 MB in the end (delta: 184.4 MB). Peak memory consumption was 184.4 MB. Max. memory is 11.5 GB. * Witness Printer took 56.72 ms. Allocated memory is still 1.1 GB. Free memory is still 910.7 MB. There was no memory consumed. Max. memory is 11.5 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - PositiveResult [Line: 6]: call of __VERIFIER_error() unreachable For all program executions holds that call of __VERIFIER_error() unreachable at this location - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 14]: Loop Invariant Derived loop invariant: (x <= 1 && 1 <= x) && 4294967296 * (y / 4294967296) + x <= y - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 20 locations, 1 error locations. SAFE Result, 10.1s OverallTime, 4 OverallIterations, 3 TraceHistogramMax, 4.7s AutomataDifference, 0.0s DeadEndRemovalTime, 0.1s HoareAnnotationTime, HoareTripleCheckerStatistics: 52 SDtfs, 11 SDslu, 87 SDs, 0 SdLazy, 69 SolverSat, 5 SolverUnsat, 2 SolverUnknown, 0 SolverNotchecked, 4.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 78 GetRequests, 47 SyntacticMatches, 3 SemanticMatches, 28 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 3.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=20occurred in iteration=0, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 1.0s AbstIntTime, 2 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 4 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 7 LocationsWithAnnotation, 10 PreInvPairs, 14 NumberOfFragments, 28 HoareAnnotationTreeSize, 10 FomulaSimplifications, 27 FormulaSimplificationTreeSizeReduction, 0.0s HoareSimplificationTime, 7 FomulaSimplificationsInter, 35 FormulaSimplificationTreeSizeReductionInter, 0.0s HoareSimplificationTimeInter, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 3.6s InterpolantComputationTime, 89 NumberOfCodeBlocks, 89 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 83 ConstructedInterpolants, 0 QuantifiedInterpolants, 9227 SizeOfPredicates, 3 NumberOfNonLiveVariables, 67 ConjunctsInSsa, 29 ConjunctsInUnsatCore, 6 InterpolantComputations, 5 PerfectInterpolantSequences, 16/18 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be correct! Received shutdown request...