gollvm: tree integrity checking enhancements
Integrity checker now has an explicit "batch" and "incremental"
mode. Batch mode processes an entire subtree, whereas incremental mode
looks only at a node's immediate children. Bridge uses batch mode at
statement creation time, incremental mode at expression creation time
(performing the check here identifies problems earlier on, making for
easier debugging). For incremental mode, rework things to avoid "false
positives" (reporting tree sharing that in fact be will be repaired
later on). Also, disable checking during tree repair/cloning
operations, since things can be in an inconsistent state at that
point.
Change-Id: Iaf754c4b5ab01cfe819f194e9655321aa2513785
Reviewed-on: https://go-review.googlesource.com/43951
Reviewed-by: Ian Lance Taylor <iant@golang.org>
diff --git a/llvm-gofrontend/go-llvm-bnode.cpp b/llvm-gofrontend/go-llvm-bnode.cpp
index 741118a9..2a00db1 100644
--- a/llvm-gofrontend/go-llvm-bnode.cpp
+++ b/llvm-gofrontend/go-llvm-bnode.cpp
@@ -295,10 +295,17 @@
return u.label;
}
+Operator Bnode::op() const
+{
+ assert(flavor() == N_UnaryOp || flavor() == N_BinaryOp);
+ return u.op;
+}
+
//......................................................................
BnodeBuilder::BnodeBuilder(Llvm_backend *be)
- : integrityVisitor_(new IntegrityVisitor(be, TreeIntegCtl(DumpPointers, IgnoreVarExprs, DontRepairSharing)))
+ : integrityVisitor_(new IntegrityVisitor(be, TreeIntegCtl(DumpPointers, IgnoreVarExprs, DontReportRepairableSharing, IncrementalMode)))
+ , checkIntegrity_(true)
{
}
@@ -334,9 +341,9 @@
void BnodeBuilder::checkTreeInteg(Bnode *node)
{
- for (unsigned idx = 0; idx < node->kids_.size(); ++idx) {
- Bnode *kid = node->kids_[idx];
- integrityVisitor_->setParent(kid, node, idx);
+ if (checkIntegrity_ && !integrityVisitor_->examine(node)) {
+ std::cerr << integrityVisitor_->msg();
+ assert(false);
}
}
@@ -740,8 +747,8 @@
newChildren.push_back(clc);
}
Bexpression *res = new Bexpression(*expr);
- archive(res);
res->kids_ = newChildren;
+ archive(res);
llvm::Value *iv = expr->value();
llvm::Value *newv = nullptr;
diff --git a/llvm-gofrontend/go-llvm-bnode.h b/llvm-gofrontend/go-llvm-bnode.h
index 3f556c0..d110c62 100644
--- a/llvm-gofrontend/go-llvm-bnode.h
+++ b/llvm-gofrontend/go-llvm-bnode.h
@@ -107,6 +107,7 @@
unsigned id() const { return id_; }
const char *flavstr() const;
LabelId label() const;
+ Operator op() const; // for unary and binary op nodes
// debugging
void dump();
@@ -270,6 +271,12 @@
// node (after which the old node will be thrown away). Returns
std::vector<Bexpression *> extractChildenAndDestroy(Bexpression *expr);
+ // Get/set whether the tree integrity checker is enabled. It makes sense
+ // to turn off the integrity checker during tree cloning operations
+ // (part of sharing repair), and also for unit testing.
+ bool integrityChecksEnabled() const { return checkIntegrity_; }
+ void setIntegrityChecks(bool val) { checkIntegrity_ = val; }
+
private:
void appendInstIfNeeded(Bexpression *rval, llvm::Value *val);
Bexpression *archive(Bexpression *expr);
@@ -285,6 +292,7 @@
std::vector<Bstatement *> sarchive_;
std::vector<SwitchDescriptor*> swcases_;
std::unique_ptr<IntegrityVisitor> integrityVisitor_;
+ bool checkIntegrity_;
};
// This class helps automate walking of a Bnode subtree; it invokes
diff --git a/llvm-gofrontend/go-llvm-tree-integrity.cpp b/llvm-gofrontend/go-llvm-tree-integrity.cpp
index f396c51..10d912c 100644
--- a/llvm-gofrontend/go-llvm-tree-integrity.cpp
+++ b/llvm-gofrontend/go-llvm-tree-integrity.cpp
@@ -107,6 +107,17 @@
unsigned prevSlot = pps.second;
if (prevParent == parent && prevSlot == slot)
return;
+ parslot ps = std::make_pair(parent, slot);
+ sharing_.push_back(std::make_pair(child, ps));
+
+ // If the sharing at this subtree is repairable, don't
+ // log an error, since the sharing will be undone later on.
+ Bexpression *expr = child->castToBexpression();
+ if (expr != nullptr &&
+ doRepairs() == DontReportRepairableSharing &&
+ repairableSubTree(expr))
+ return;
+
const char *wh = nullptr;
if (child->isStmt()) {
stmtShareCount_ += 1;
@@ -115,6 +126,8 @@
exprShareCount_ += 1;
wh = "expr";
}
+
+ // capture a description of the error
ss_ << "error: " << wh << " has multiple parents\n";
ss_ << "child " << wh << ":\n";
dump(child);
@@ -122,8 +135,7 @@
dump(prevParent);
ss_ << "parent 2:\n";
dump(parent);
- parslot ps = std::make_pair(parent, slot);
- sharing_.push_back(std::make_pair(child, ps));
+ return;
}
nparent_[child] = std::make_pair(parent, slot);
}
@@ -160,6 +172,9 @@
acceptable.insert(N_Deref);
acceptable.insert(N_StructField);
+ // Allow a limited set of these.
+ acceptable.insert(N_BinaryOp);
+
std::set<Bexpression *> visited;
visited.insert(root);
std::vector<Bexpression *> workList;
@@ -170,6 +185,10 @@
workList.pop_back();
if (acceptable.find(e->flavor()) == acceptable.end())
return false;
+ if (e->flavor() == N_BinaryOp &&
+ (e->op() != OPERATOR_PLUS &&
+ e->op() != OPERATOR_MINUS))
+ return false;
for (auto &c : e->children()) {
Bexpression *ce = c->castToBexpression();
assert(ce);
@@ -182,8 +201,23 @@
return true;
}
+class ScopedIntegrityCheckDisabler {
+ public:
+ ScopedIntegrityCheckDisabler(Llvm_backend *be)
+ : be_(be), val_(be->nodeBuilder().integrityChecksEnabled()) {
+ be_->nodeBuilder().setIntegrityChecks(false);
+ }
+ ~ScopedIntegrityCheckDisabler() {
+ be_->nodeBuilder().setIntegrityChecks(val_);
+ }
+ private:
+ Llvm_backend *be_;
+ bool val_;
+};
+
bool IntegrityVisitor::repair(Bnode *node)
{
+ ScopedIntegrityCheckDisabler disabler(be_);
std::set<Bexpression *> visited;
for (auto &p : sharing_) {
Bexpression *child = p.first->castToBexpression();
@@ -200,6 +234,8 @@
Bexpression *childClone = be_->nodeBuilder().cloneSubtree(child);
parent->replaceChild(slot, childClone);
}
+ sharing_.clear();
+ exprShareCount_ = 0;
return true;
}
@@ -207,7 +243,8 @@
{
unsigned idx = 0;
for (auto &child : node->children()) {
- visit(child);
+ if (visitMode() == BatchMode)
+ visit(child);
setParent(child, node, idx++);
}
Bexpression *expr = node->castToBexpression();
@@ -220,20 +257,28 @@
bool IntegrityVisitor::examine(Bnode *node)
{
- // Walk the tree to see what sort of sharing we have.
+ // Visit node (and possibly entire subtree at node, mode depending)
visit(node);
// Inst sharing and statement sharing are not repairable.
if (instShareCount_ != 0 || stmtShareCount_ != 0)
return false;
- if (exprShareCount_ == 0)
- return true;
-
- if (doRepairs() != RepairSharing)
+ if (exprShareCount_ != 0)
return false;
- // Attempt repair..
+ // If the checker is in incremental mode, don't attempt repairs
+ // (those will be done later on).
+ if (visitMode() == IncrementalMode) {
+ sharing_.clear();
+ return true;
+ }
+
+ // Batch mode: return now if no sharing.
+ if (sharing_.empty())
+ return true;
+
+ // Batch mode: perform repairs.
if (repair(node))
return true;
diff --git a/llvm-gofrontend/go-llvm-tree-integrity.h b/llvm-gofrontend/go-llvm-tree-integrity.h
index 3f64b7c..519fe85 100644
--- a/llvm-gofrontend/go-llvm-tree-integrity.h
+++ b/llvm-gofrontend/go-llvm-tree-integrity.h
@@ -27,7 +27,8 @@
enum CkTreePtrDisp { DumpPointers, NoDumpPointers };
enum CkTreeVarDisp { CheckVarExprs, IgnoreVarExprs };
-enum CkTreeRepairDisp { RepairSharing, DontRepairSharing };
+enum CkTreeRepairDisp { DontReportRepairableSharing, ReportRepairableSharing };
+enum CkTreeVisitDisp { BatchMode, IncrementalMode };
// Options/controls for the tree integrity checker.
@@ -35,12 +36,16 @@
CkTreePtrDisp ptrDisp;
CkTreeVarDisp varDisp;
CkTreeRepairDisp repairDisp;
+ CkTreeVisitDisp visitDisp;
TreeIntegCtl()
: ptrDisp(DumpPointers),
varDisp(CheckVarExprs),
- repairDisp(DontRepairSharing) { }
- TreeIntegCtl(CkTreePtrDisp ptrs, CkTreeVarDisp vars, CkTreeRepairDisp rep)
- : ptrDisp(ptrs), varDisp(vars), repairDisp(rep) { }
+ repairDisp(ReportRepairableSharing),
+ visitDisp(BatchMode) { }
+ TreeIntegCtl(CkTreePtrDisp ptrs, CkTreeVarDisp vars,
+ CkTreeRepairDisp repair, CkTreeVisitDisp visit)
+ : ptrDisp(ptrs), varDisp(vars),
+ repairDisp(repair), visitDisp(visit) { }
};
// This visitor class detects malformed IR trees, specifically cases
@@ -90,8 +95,23 @@
: be_(be), ss_(str_), control_(control),
instShareCount_(0), stmtShareCount_(0), exprShareCount_(0) { }
+ // Visits the node tree "n", looking for any shared nodes or
+ // instructions. Returns TRUE if there is no sharing (or if all
+ // sharing instances are repairable and repair is on), or FALSE if
+ // there is unrepairable sharing. Note that if the visit mode (in
+ // 'control' options above) is set to BatchMode, then the visitor
+ // will walk the entire subtree rooted at "n" and perform repairs
+ // after the way. Otherwise (checkers is in incremental mode), only
+ // the chidren of "n" are visited, and not repairs are performed.
bool examine(Bnode *n);
- std::string msg() { return ss_.str(); }
+
+ // Returns a message describing the nature of the node sharing (intended
+ // for a developer, not a compiler user).
+ std::string msg() { auto rv = ss_.str(); str_ = ""; return rv; }
+
+ // Tell the IntegrityVisitor to forget about the specified parent/child
+ // relationship (used when node child is deleted or repurposed).
+ void unsetParent(Bnode *child, Bnode *parent, unsigned slot);
private:
Llvm_backend *be_;
@@ -111,7 +131,6 @@
void visit(Bnode *n);
bool repairableSubTree(Bexpression *root);
bool shouldBeTracked(Bnode *child);
- void unsetParent(Bnode *child, Bnode *parent, unsigned slot);
void setParent(Bnode *child, Bnode *parent, unsigned slot);
void setParent(llvm::Instruction *inst, Bexpression *par, unsigned slot);
void dumpTag(const char *tag, void *ptr);
@@ -120,6 +139,7 @@
CkTreePtrDisp includePointers() const { return control_.ptrDisp; }
CkTreeVarDisp includeVarExprs() const { return control_.varDisp; }
CkTreeRepairDisp doRepairs() const { return control_.repairDisp; }
+ CkTreeVisitDisp visitMode() const { return control_.visitDisp; }
friend BnodeBuilder;
};
diff --git a/llvm-gofrontend/go-llvm.cpp b/llvm-gofrontend/go-llvm.cpp
index ccf1ce8..5a8474f 100644
--- a/llvm-gofrontend/go-llvm.cpp
+++ b/llvm-gofrontend/go-llvm.cpp
@@ -176,7 +176,8 @@
{
if (e) {
e->srcDump(linemap_);
- TreeIntegCtl ctl(DumpPointers, IgnoreVarExprs, DontRepairSharing);
+ TreeIntegCtl ctl(DumpPointers, IgnoreVarExprs,
+ ReportRepairableSharing, BatchMode);
auto p = checkTreeIntegrity(e, ctl);
if (p.first)
std::cerr << p.second;
@@ -187,7 +188,8 @@
{
if (s) {
s->srcDump(linemap_);
- TreeIntegCtl ctl(DumpPointers, IgnoreVarExprs, DontRepairSharing);
+ TreeIntegCtl ctl(DumpPointers, IgnoreVarExprs,
+ ReportRepairableSharing, BatchMode);
auto p = checkTreeIntegrity(s, ctl);
if (p.first)
std::cerr << p.second;
@@ -212,7 +214,8 @@
void Llvm_backend::enforceTreeIntegrity(Bnode *n)
{
Llvm_backend *be = const_cast<Llvm_backend *>(this);
- TreeIntegCtl control(DumpPointers, IgnoreVarExprs, RepairSharing);
+ TreeIntegCtl control(DumpPointers, IgnoreVarExprs,
+ DontReportRepairableSharing, BatchMode);
IntegrityVisitor iv(be, control);
bool res = iv.examine(n);
if (!res && checkIntegrity_) {
diff --git a/unittests/BackendCore/BackendTreeIntegrity.cpp b/unittests/BackendCore/BackendTreeIntegrity.cpp
index a39a0cc..ae0c4ca 100644
--- a/unittests/BackendCore/BackendTreeIntegrity.cpp
+++ b/unittests/BackendCore/BackendTreeIntegrity.cpp
@@ -45,7 +45,8 @@
for (auto inst : badd1->instructions())
b4->appendInstruction(inst);
- TreeIntegCtl control(NoDumpPointers, CheckVarExprs, DontRepairSharing);
+ TreeIntegCtl control(NoDumpPointers, CheckVarExprs,
+ ReportRepairableSharing, BatchMode);
std::pair<bool, std::string> result =
be->checkTreeIntegrity(h.block(), control);
EXPECT_FALSE(result.first);
@@ -77,7 +78,8 @@
Bstatement *es2 = be->expression_statement(func, ve);
addStmtToBlock(be.get(), block, es2);
- TreeIntegCtl control(NoDumpPointers, CheckVarExprs, DontRepairSharing);
+ TreeIntegCtl control(NoDumpPointers, CheckVarExprs,
+ ReportRepairableSharing, BatchMode);
std::pair<bool, std::string> result =
be->checkTreeIntegrity(block, control);
EXPECT_FALSE(result.first);
@@ -107,7 +109,8 @@
Bblock *block = mkBlockFromStmt(be.get(), func, es);
addStmtToBlock(be.get(), block, es);
- TreeIntegCtl control(NoDumpPointers, CheckVarExprs, DontRepairSharing);
+ TreeIntegCtl control(NoDumpPointers, CheckVarExprs,
+ ReportRepairableSharing, BatchMode);
std::pair<bool, std::string> result =
be->checkTreeIntegrity(block, control);
EXPECT_FALSE(result.first);
