From 502942a53a6db2b3a900d7570807216372d49ad0 Mon Sep 17 00:00:00 2001 From: Valentin Wüstholz Date: Thu, 3 Mar 2016 17:32:31 -0600 Subject: Improve support for optimization and identifying unnecessary assumes. --- Source/Provers/SMTLib/ProverInterface.cs | 34 ++++++++++++------------------ Source/Provers/SMTLib/SMTLibLineariser.cs | 22 +++++++++++++++++-- Source/Provers/SMTLib/TypeDeclCollector.cs | 12 +++++++++-- 3 files changed, 43 insertions(+), 25 deletions(-) (limited to 'Source/Provers/SMTLib') diff --git a/Source/Provers/SMTLib/ProverInterface.cs b/Source/Provers/SMTLib/ProverInterface.cs index 7e98e8f8..432d7f3e 100644 --- a/Source/Provers/SMTLib/ProverInterface.cs +++ b/Source/Provers/SMTLib/ProverInterface.cs @@ -411,15 +411,6 @@ namespace Microsoft.Boogie.SMTLib SendThisVC("(push 1)"); SendThisVC("(set-info :boogie-vc-id " + SMTLibNamer.QuoteId(descriptiveName) + ")"); - if (CommandLineOptions.Clo.PrintNecessaryAssumes && NamedAssumeVars != null) - { - foreach (var v in NamedAssumeVars) - { - SendThisVC(string.Format("(declare-fun {0} () Bool)", v)); - SendThisVC(string.Format("(assert (! {0} :named {1}))", v, "aux$$" + v.Name)); - } - } - SendThisVC(vcString); SendOptimizationRequests(); @@ -1293,7 +1284,7 @@ namespace Microsoft.Boogie.SMTLib var reporter = handler as VC.VCGen.ErrorReporter; // TODO(wuestholz): Is the reporter ever null? - if (CommandLineOptions.Clo.PrintNecessaryAssumes && NamedAssumeVars != null && NamedAssumeVars.Any() && result == Outcome.Valid && reporter != null) + if (CommandLineOptions.Clo.PrintNecessaryAssumes && ContainsNamedAssumes && result == Outcome.Valid && reporter != null) { SendThisVC("(get-unsat-core)"); var resp = Process.GetProverResponse(); @@ -1993,6 +1984,8 @@ namespace Microsoft.Boogie.SMTLib readonly IList OptimizationRequests = new List(); + bool ContainsNamedAssumes; + protected string VCExpr2String(VCExpr expr, int polarity) { Contract.Requires(expr != null); @@ -2032,8 +2025,8 @@ namespace Microsoft.Boogie.SMTLib DeclCollector.Collect(sortedExpr); FeedTypeDeclsToProver(); - AddAxiom(SMTLibExprLineariser.ToString(sortedAxioms, Namer, options)); - string res = SMTLibExprLineariser.ToString(sortedExpr, Namer, options, OptimizationRequests); + AddAxiom(SMTLibExprLineariser.ToString(sortedAxioms, Namer, options, ref ContainsNamedAssumes)); + string res = SMTLibExprLineariser.ToString(sortedExpr, Namer, options, ref ContainsNamedAssumes, OptimizationRequests); Contract.Assert(res != null); if (CommandLineOptions.Clo.Trace) @@ -2141,20 +2134,19 @@ namespace Microsoft.Boogie.SMTLib throw new NotImplementedException(); } - public override void Assert(VCExpr vc, bool polarity) + public override void Assert(VCExpr vc, bool polarity, bool isSoft = false, int weight = 1) { OptimizationRequests.Clear(); - string a = ""; - if (polarity) - { - a = "(assert " + VCExpr2String(vc, 1) + ")"; + string assert = "assert"; + if (options.Solver == SolverKind.Z3 && isSoft) { + assert += "-soft"; } - else - { - a = "(assert (not\n" + VCExpr2String(vc, 1) + "\n))"; + var expr = polarity ? VCExpr2String(vc, 1) : "(not\n" + VCExpr2String(vc, 1) + "\n)"; + if (options.Solver == SolverKind.Z3 && isSoft) { + expr += " :weight " + weight; } AssertAxioms(); - SendThisVC(a); + SendThisVC("(" + assert + " " + expr + ")"); SendOptimizationRequests(); } diff --git a/Source/Provers/SMTLib/SMTLibLineariser.cs b/Source/Provers/SMTLib/SMTLibLineariser.cs index de8798b8..6df44c2f 100644 --- a/Source/Provers/SMTLib/SMTLibLineariser.cs +++ b/Source/Provers/SMTLib/SMTLibLineariser.cs @@ -34,7 +34,7 @@ namespace Microsoft.Boogie.SMTLib public class SMTLibExprLineariser : IVCExprVisitor { - public static string ToString(VCExpr e, UniqueNamer namer, SMTLibProverOptions opts, IList optReqs = null) + public static string ToString(VCExpr e, UniqueNamer namer, SMTLibProverOptions opts, ref bool containsNamedAssumes, IList optReqs = null) { Contract.Requires(e != null); Contract.Requires(namer != null); @@ -44,6 +44,7 @@ namespace Microsoft.Boogie.SMTLib SMTLibExprLineariser lin = new SMTLibExprLineariser(sw, namer, opts, optReqs); Contract.Assert(lin != null); lin.Linearise(e, LineariserOptions.Default); + containsNamedAssumes |= lin.ContainsNamedAssumes; return cce.NonNull(sw.ToString()); } @@ -76,6 +77,12 @@ namespace Microsoft.Boogie.SMTLib readonly IList OptimizationRequests; + bool containsNamedAssumes; + public bool ContainsNamedAssumes + { + get { return containsNamedAssumes; } + } + public SMTLibExprLineariser(TextWriter wr, UniqueNamer namer, SMTLibProverOptions opts, IList optReqs = null) { Contract.Requires(wr != null); Contract.Requires(namer != null); @@ -270,7 +277,18 @@ namespace Microsoft.Boogie.SMTLib && (node.Op.Equals(VCExpressionGenerator.MinimizeOp) || node.Op.Equals(VCExpressionGenerator.MaximizeOp))) { string optOp = node.Op.Equals(VCExpressionGenerator.MinimizeOp) ? "minimize" : "maximize"; - OptimizationRequests.Add(string.Format("({0} {1})", optOp, ToString(node[0], Namer, ProverOptions))); + OptimizationRequests.Add(string.Format("({0} {1})", optOp, ToString(node[0], Namer, ProverOptions, ref containsNamedAssumes))); + Linearise(node[1], options); + return true; + } + if (node.Op.Equals(VCExpressionGenerator.SoftOp)) + { + Linearise(node[1], options); + return true; + } + if (node.Op.Equals(VCExpressionGenerator.NamedAssumeOp)) + { + containsNamedAssumes = true; Linearise(node[1], options); return true; } diff --git a/Source/Provers/SMTLib/TypeDeclCollector.cs b/Source/Provers/SMTLib/TypeDeclCollector.cs index 1c23c22f..72540c9c 100644 --- a/Source/Provers/SMTLib/TypeDeclCollector.cs +++ b/Source/Provers/SMTLib/TypeDeclCollector.cs @@ -210,7 +210,15 @@ void ObjectInvariant() if (node.Op is VCExprStoreOp) RegisterStore(node); else if (node.Op is VCExprSelectOp) RegisterSelect(node); - else { + else if (node.Op.Equals(VCExpressionGenerator.SoftOp)) { + var exprVar = node[0] as VCExprVar; + AddDeclaration(string.Format("(declare-fun {0} () Bool)", exprVar.Name)); + AddDeclaration(string.Format("(assert-soft {0} :weight 1)", exprVar.Name)); + } else if (node.Op.Equals(VCExpressionGenerator.NamedAssumeOp)) { + var exprVar = node[0] as VCExprVar; + AddDeclaration(string.Format("(declare-fun {0} () Bool)", exprVar.Name)); + AddDeclaration(string.Format("(assert (! {0} :named {1}))", exprVar.Name, "aux$$" + exprVar.Name)); + } else { VCExprBoogieFunctionOp op = node.Op as VCExprBoogieFunctionOp; if (op != null && !(op.Func is DatatypeConstructor) && !(op.Func is DatatypeMembership) && !(op.Func is DatatypeSelector) && @@ -255,7 +263,7 @@ void ObjectInvariant() RegisterType(node.Type); string decl = "(declare-fun " + printedName + " () " + TypeToString(node.Type) + ")"; - if (!printedName.StartsWith("assume$$")) + if (!(printedName.StartsWith("assume$$") || printedName.StartsWith("soft$$"))) { AddDeclaration(decl); } -- cgit v1.2.3