Subzero: fix non-deterministic stack layout and code-gen
Using std::unordered_set to hold unmaterialized variables meant that
when materializeAll was called, the order of variables would differ
between runs of the same executable on the same target.
Instead, we now use a map of Variable* to a monotonically increasing
counter, allowing us to not only guarantee order-consistency across
runs, but also means we can submit variables in the order they are
declared, which may be preferable by the JIT backend.
Note that this also affects LLVM; however, LLVM likely already performs
stack variable reordering, so the effects are minimized. Nonetheless,
this change likely also fixes determinism when using LLVM.
Bug: angleproject:4482
Bug: b/172365901
Change-Id: I5698085ab96663b3c9a2fae4f01b1c1b3aac8b4b
Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/49949
Presubmit-Ready: Antonio Maiorano <amaiorano@google.com>
Tested-by: Antonio Maiorano <amaiorano@google.com>
Kokoro-Result: kokoro <noreply+kokoro@google.com>
Reviewed-by: Nicolas Capens <nicolascapens@google.com>
diff --git a/src/Reactor/LLVMReactor.cpp b/src/Reactor/LLVMReactor.cpp
index 4aee82d..31491c3 100644
--- a/src/Reactor/LLVMReactor.cpp
+++ b/src/Reactor/LLVMReactor.cpp
@@ -504,7 +504,7 @@
#endif
jit = new JITBuilder(Nucleus::getDefaultConfig());
- Variable::unmaterializedVariables = new std::unordered_set<const Variable *>();
+ Variable::unmaterializedVariables = new Variable::UnmaterializedVariables{};
}
Nucleus::~Nucleus()
diff --git a/src/Reactor/Reactor.cpp b/src/Reactor/Reactor.cpp
index d342595..4ea9ebe 100644
--- a/src/Reactor/Reactor.cpp
+++ b/src/Reactor/Reactor.cpp
@@ -64,17 +64,54 @@
}
}
-// Set of variables that do not have a stack location yet.
-thread_local std::unordered_set<const Variable *> *Variable::unmaterializedVariables = nullptr;
+thread_local Variable::UnmaterializedVariables *Variable::unmaterializedVariables = nullptr;
+
+void Variable::UnmaterializedVariables::add(const Variable *v)
+{
+ variables.emplace(v, counter++);
+}
+
+void Variable::UnmaterializedVariables::remove(const Variable *v)
+{
+ auto iter = variables.find(v);
+ if(iter != variables.end())
+ {
+ variables.erase(iter);
+ }
+}
+
+void Variable::UnmaterializedVariables::clear()
+{
+ variables.clear();
+}
+
+void Variable::UnmaterializedVariables::materializeAll()
+{
+ // Flatten map of Variable* to monotonically increasing counter to a vector,
+ // then sort it by the counter, so that we materialize in variable usage order.
+ std::vector<std::pair<const Variable *, int>> sorted;
+ sorted.resize(variables.size());
+ std::copy(variables.begin(), variables.end(), sorted.begin());
+ std::sort(sorted.begin(), sorted.end(), [&](auto &lhs, auto &rhs) {
+ return lhs.second < rhs.second;
+ });
+
+ for(auto &v : sorted)
+ {
+ v.first->materialize();
+ }
+
+ variables.clear();
+}
Variable::Variable()
{
- unmaterializedVariables->emplace(this);
+ unmaterializedVariables->add(this);
}
Variable::~Variable()
{
- unmaterializedVariables->erase(this);
+ unmaterializedVariables->remove(this);
}
void Variable::materialize() const
@@ -139,12 +176,7 @@
void Variable::materializeAll()
{
- for(auto *var : *unmaterializedVariables)
- {
- var->materialize();
- }
-
- unmaterializedVariables->clear();
+ unmaterializedVariables->materializeAll();
}
void Variable::killUnmaterialized()
diff --git a/src/Reactor/Reactor.hpp b/src/Reactor/Reactor.hpp
index e301976..77cf3af 100644
--- a/src/Reactor/Reactor.hpp
+++ b/src/Reactor/Reactor.hpp
@@ -24,7 +24,7 @@
#include <cstdio>
#include <limits>
#include <tuple>
-#include <unordered_set>
+#include <unordered_map>
#ifdef ENABLE_RR_DEBUG_INFO
// Functions used for generating JIT debug info.
@@ -132,9 +132,23 @@
virtual Value *allocate() const;
+ // Set of variables that do not have a stack location yet.
+ class UnmaterializedVariables
+ {
+ public:
+ void add(const Variable *v);
+ void remove(const Variable *v);
+ void clear();
+ void materializeAll();
+
+ private:
+ int counter = 0;
+ std::unordered_map<const Variable *, int> variables;
+ };
+
// This has to be a raw pointer because glibc 2.17 doesn't support __cxa_thread_atexit_impl
// for destructing objects at exit. See crbug.com/1074222
- static thread_local std::unordered_set<const Variable *> *unmaterializedVariables;
+ static thread_local UnmaterializedVariables *unmaterializedVariables;
mutable Value *rvalue = nullptr;
mutable Value *address = nullptr;
diff --git a/src/Reactor/SubzeroReactor.cpp b/src/Reactor/SubzeroReactor.cpp
index 85c99e3..21787b8 100644
--- a/src/Reactor/SubzeroReactor.cpp
+++ b/src/Reactor/SubzeroReactor.cpp
@@ -909,7 +909,7 @@
// instrumented, leading to false-positive unitialized variable errors.
ASSERT(Variable::unmaterializedVariables == nullptr);
#endif
- Variable::unmaterializedVariables = new std::unordered_set<const Variable *>();
+ Variable::unmaterializedVariables = new Variable::UnmaterializedVariables{};
}
Nucleus::~Nucleus()
