From 29d010c291558a4199b5116d312f32cad86807e7 Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Wed, 23 Dec 2015 12:19:22 +0000 Subject: [NFC] Reformat ``getAllIndependentConstraintsSets()`` using clang-format. It was not formatted correctly and was consequently a little hard to read. Also add braces around a for loop body. The original code for this function came from d9bcbba2c94086039c11c86200670639ee2ec19f --- lib/Solver/IndependentSolver.cpp | 70 ++++++++++++++++++++++------------------ 1 file changed, 38 insertions(+), 32 deletions(-) diff --git a/lib/Solver/IndependentSolver.cpp b/lib/Solver/IndependentSolver.cpp index a7685e46..6b5a5586 100644 --- a/lib/Solver/IndependentSolver.cpp +++ b/lib/Solver/IndependentSolver.cpp @@ -258,53 +258,59 @@ inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os, // Breaks down a constraint into all of it's individual pieces, returning a // list of IndependentElementSets or the independent factors. -static -void getAllIndependentConstraintsSets(const Query& query, - std::list * &factors){ +static void +getAllIndependentConstraintsSets(const Query &query, + std::list *&factors) { ConstantExpr *CE = dyn_cast(query.expr); - if (CE){ - assert(CE && CE->isFalse() && - "the expr should always be false and therefore not included in factors"); + if (CE) { + assert(CE && CE->isFalse() && "the expr should always be false and " + "therefore not included in factors"); } else { ref neg = Expr::createIsZero(query.expr); factors->push_back(IndependentElementSet(neg)); } for (ConstraintManager::const_iterator it = query.constraints.begin(), - ie = query.constraints.end(); it != ie; ++it) + ie = query.constraints.end(); + it != ie; ++it) { // iterate through all the previously separated constraints. Until we // actually return, factors is treated as a queue of expressions to be // evaluated. If the queue property isn't maintained, then the exprs // could be returned in an order different from how they came it, negatively // affecting later stages. factors->push_back(IndependentElementSet(*it)); - bool doneLoop = false; - do { - doneLoop = true; - std::list * done = new std::list; - while (factors->size() > 0){ - IndependentElementSet current = factors->front(); + } + + bool doneLoop = false; + do { + doneLoop = true; + std::list *done = + new std::list; + while (factors->size() > 0) { + IndependentElementSet current = factors->front(); + factors->pop_front(); + // This list represents the set of factors that are separate from current. + // Those that are not inserted into this list (queue) intersect with + // current. + std::list *keep = + new std::list; + while (factors->size() > 0) { + IndependentElementSet compare = factors->front(); factors->pop_front(); - // This list represents the set of factors that are separate from current. - // Those that are not inserted into this list (queue) intersect with current. - std::list *keep = new std::list; - while (factors->size() > 0){ - IndependentElementSet compare = factors->front(); - factors->pop_front(); - if (current.intersects(compare)){ - if (current.add(compare)){ - // Means that we have added (z=y)added to (x=y) - // Now need to see if there are any (z=?)'s - doneLoop = false; - } - } else { - keep->push_back(compare); - } - } - done->push_back(current); - delete factors; - factors = keep; + if (current.intersects(compare)) { + if (current.add(compare)) { + // Means that we have added (z=y)added to (x=y) + // Now need to see if there are any (z=?)'s + doneLoop = false; + } + } else { + keep->push_back(compare); + } } + done->push_back(current); + delete factors; + factors = keep; + } delete factors; factors = done; } while (!doneLoop); -- cgit 1.4.1 From c8b3c00f1f15952ea4bcbeb9c633f9e8ebc8a6bf Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Wed, 23 Dec 2015 12:30:54 +0000 Subject: Fix memory leak detected by ASan when ``IndependentSolver::computeInitialValues()`` was called where at least one of the constraint sets computed by ``getAllIndependentConstraintsSets()`` is either unsatisfiable or the solver failed. To make things (a little) clearer I've made it so that no ``std::list<>*`` is passed to``getAllIndependentConstraintsSets()``. Instead ``getAllIndependentConstraintsSets()`` now returns a ``std::list<>*`` that the caller is responsible for cleaning up. The behaviour previously was really confusing because it was unclear if the caller or callee was responsible for the clean up. This fixes #322 --- lib/Solver/IndependentSolver.cpp | 18 ++++++++++++------ 1 file changed, 12 insertions(+), 6 deletions(-) diff --git a/lib/Solver/IndependentSolver.cpp b/lib/Solver/IndependentSolver.cpp index 6b5a5586..78126ede 100644 --- a/lib/Solver/IndependentSolver.cpp +++ b/lib/Solver/IndependentSolver.cpp @@ -258,9 +258,11 @@ inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os, // Breaks down a constraint into all of it's individual pieces, returning a // list of IndependentElementSets or the independent factors. -static void -getAllIndependentConstraintsSets(const Query &query, - std::list *&factors) { +// +// Caller takes ownership of returned std::list. +static std::list* +getAllIndependentConstraintsSets(const Query &query) { + std::list *factors = new std::list(); ConstantExpr *CE = dyn_cast(query.expr); if (CE) { assert(CE && CE->isFalse() && "the expr should always be false and " @@ -314,6 +316,8 @@ getAllIndependentConstraintsSets(const Query &query, delete factors; factors = done; } while (!doneLoop); + + return factors; } static @@ -459,14 +463,14 @@ bool IndependentSolver::computeInitialValues(const Query& query, const std::vector &objects, std::vector< std::vector > &values, bool &hasSolution){ - std::list * factors = new std::list; - // We assume the query has a solution except proven differently // This is important in case we don't have any constraints but // we need initial values for requested array objects. hasSolution = true; + // FIXME: When we switch to C++11 this should be a std::unique_ptr so we don't need + // to remember to manually call delete + std::list *factors = getAllIndependentConstraintsSets(query); - getAllIndependentConstraintsSets(query, factors); //Used to rearrange all of the answers into the correct order std::map > retMap; for (std::list::iterator it = factors->begin(); @@ -483,9 +487,11 @@ bool IndependentSolver::computeInitialValues(const Query& query, if (!solver->impl->computeInitialValues(Query(tmp, ConstantExpr::alloc(0, Expr::Bool)), arraysInFactor, tempValues, hasSolution)){ values.clear(); + delete factors; return false; } else if (!hasSolution){ values.clear(); + delete factors; return true; } else { assert(tempValues.size() == arraysInFactor.size() && -- cgit 1.4.1