From: Nicolas Capens Date: Wed, 27 Mar 2019 18:46:07 +0000 (-0400) Subject: Elide single basic block variable materialization X-Git-Tag: android-x86-9.0-r1~34 X-Git-Url: http://git.osdn.net/view?p=android-x86%2Fexternal-swiftshader.git;a=commitdiff_plain;h=0192d15debf07e7d4d365aef8a1f37a9bbfe22a4 Elide single basic block variable materialization Variables which are only used within a single basic block and don't have their address taken, don't require allocating stack memory. Instead they can track the latest rvalue that has been assigned to them. Allocating stack memory is necessary for variables that are assigned to in divergent basic blocks since there is no single rvalue to track after the merge point (unless we inserted phi instructions, but that is outside of the scope of this change). Because Reactor can't look forward to check whether a variable will be used in divergent basic blocks, we keep the set of variables that may not have been materialized yet, meaning they have no stack address yet. When a branch is encountered, they are all materialized. Variables not yet materialized at a Return() are 'killed' to prevent materializing afterwards, which would cause the terminator ret instruction to not be the last instruction of the basic block. Note that this change creates a dependency of the Nucleus implementation on Variable, which is currently defined in a higher layer in Reactor.hpp. Since Variable doesn't depend on anything else in Reactor.hpp it could be made part of Nucleus, or an in-between layer could be added. Bug b/129356087 Change-Id: Ie8c09e34c8befb9787a5c0bca7a20e770bcbf8d3 Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/27928 Tested-by: Nicolas Capens Presubmit-Ready: Nicolas Capens Reviewed-by: Ben Clayton --- diff --git a/src/Reactor/LLVMReactor.cpp b/src/Reactor/LLVMReactor.cpp index 624af832f..55ca0495c 100644 --- a/src/Reactor/LLVMReactor.cpp +++ b/src/Reactor/LLVMReactor.cpp @@ -1052,6 +1052,9 @@ namespace rr void Nucleus::setInsertBlock(BasicBlock *basicBlock) { // assert(::builder->GetInsertBlock()->back().isTerminator()); + + Variable::materializeAll(); + ::builder->SetInsertPoint(B(basicBlock)); } @@ -1090,21 +1093,35 @@ namespace rr void Nucleus::createRetVoid() { + // Code generated after this point is unreachable, so any variables + // being read can safely return an undefined value. We have to avoid + // materializing variables after the terminator ret instruction. + Variable::killUnmaterialized(); + ::builder->CreateRetVoid(); } void Nucleus::createRet(Value *v) { + // Code generated after this point is unreachable, so any variables + // being read can safely return an undefined value. We have to avoid + // materializing variables after the terminator ret instruction. + Variable::killUnmaterialized(); + ::builder->CreateRet(V(v)); } void Nucleus::createBr(BasicBlock *dest) { + Variable::materializeAll(); + ::builder->CreateBr(B(dest)); } void Nucleus::createCondBr(Value *cond, BasicBlock *ifTrue, BasicBlock *ifFalse) { + Variable::materializeAll(); + ::builder->CreateCondBr(V(cond), B(ifTrue), B(ifFalse)); } diff --git a/src/Reactor/Reactor.cpp b/src/Reactor/Reactor.cpp index 559cb4f29..b0225335e 100644 --- a/src/Reactor/Reactor.cpp +++ b/src/Reactor/Reactor.cpp @@ -14,8 +14,46 @@ #include "Reactor.hpp" +// Define REACTOR_MATERIALIZE_LVALUES_ON_DEFINITION to non-zero to ensure all +// variables have a stack location obtained throuch alloca(). +#ifndef REACTOR_MATERIALIZE_LVALUES_ON_DEFINITION +#define REACTOR_MATERIALIZE_LVALUES_ON_DEFINITION 0 +#endif + namespace rr { + // Set of variables that do not have a stack location yet. + std::unordered_set Variable::unmaterializedVariables; + + Variable::Variable(Type *type, int arraySize) : type(type), arraySize(arraySize) + { + #if REACTOR_MATERIALIZE_LVALUES_ON_DEFINITION + materialize(); + #else + unmaterializedVariables.emplace(this); + #endif + } + + Variable::~Variable() + { + unmaterializedVariables.erase(this); + } + + void Variable::materializeAll() + { + for(auto *var : unmaterializedVariables) + { + var->materialize(); + } + + unmaterializedVariables.clear(); + } + + void Variable::killUnmaterialized() + { + unmaterializedVariables.clear(); + } + static Value *createSwizzle4(Value *val, unsigned char select) { int swizzle[4] = diff --git a/src/Reactor/Reactor.hpp b/src/Reactor/Reactor.hpp index ebf2a7a0a..ee473a63f 100644 --- a/src/Reactor/Reactor.hpp +++ b/src/Reactor/Reactor.hpp @@ -24,6 +24,7 @@ #include #include +#include #undef Bool // b/127920555 @@ -81,16 +82,37 @@ namespace rr class Variable { + friend class Nucleus; friend class PrintValue; + Variable() = delete; Variable &operator=(const Variable&) = delete; public: - Variable() = default; - Variable(const Variable&) = default; + void materialize() const; + + Value *loadValue() const; + Value *storeValue(Value *value) const; + + Value *getBaseAddress() const; + Value *getElementPointer(Value *index, bool unsignedIndex) const; protected: - Value *address; + Variable(Type *type, int arraySize); + Variable(const Variable&) = default; + + ~Variable(); + + private: + static void materializeAll(); + static void killUnmaterialized(); + + static std::unordered_set unmaterializedVariables; + + Type *const type; + const int arraySize; + mutable Value *rvalue = nullptr; + mutable Value *address = nullptr; }; template @@ -105,10 +127,6 @@ namespace rr { return false; } - - Value *loadValue() const; - Value *storeValue(Value *value) const; - Value *getAddress(Value *index, bool unsignedIndex) const; }; template @@ -2320,33 +2338,68 @@ namespace rr namespace rr { template - LValue::LValue(int arraySize) + LValue::LValue(int arraySize) : Variable(T::getType(), arraySize) { - address = Nucleus::allocateStackVariable(T::getType(), arraySize); } - template - Value *LValue::loadValue() const + inline void Variable::materialize() const + { + if(!address) + { + address = Nucleus::allocateStackVariable(type, arraySize); + + if(rvalue) + { + storeValue(rvalue); + rvalue = nullptr; + } + } + } + + inline Value *Variable::loadValue() const + { + if(rvalue) + { + return rvalue; + } + + if(!address) + { + // TODO: Return undef instead. + materialize(); + } + + return Nucleus::createLoad(address, type, false, 0); + } + + inline Value *Variable::storeValue(Value *value) const { - return Nucleus::createLoad(address, T::getType(), false, 0); + if(address) + { + return Nucleus::createStore(value, address, type, false, 0); + } + + rvalue = value; + + return value; } - template - Value *LValue::storeValue(Value *value) const + inline Value *Variable::getBaseAddress() const { - return Nucleus::createStore(value, address, T::getType(), false, 0); + materialize(); + + return address; } - template - Value *LValue::getAddress(Value *index, bool unsignedIndex) const + inline Value *Variable::getElementPointer(Value *index, bool unsignedIndex) const { - return Nucleus::createGEP(address, T::getType(), index, unsignedIndex); + return Nucleus::createGEP(getBaseAddress(), type, index, unsignedIndex); } template RValue> LValue::operator&() { - return RValue>(address); + return RValue>(getBaseAddress()); } template @@ -2680,7 +2733,7 @@ namespace rr template Reference Array::operator[](int index) { - Value *element = LValue::getAddress(Nucleus::createConstantInt(index), false); + Value *element = LValue::getElementPointer(Nucleus::createConstantInt(index), false); return Reference(element); } @@ -2688,7 +2741,7 @@ namespace rr template Reference Array::operator[](unsigned int index) { - Value *element = LValue::getAddress(Nucleus::createConstantInt(index), true); + Value *element = LValue::getElementPointer(Nucleus::createConstantInt(index), true); return Reference(element); } @@ -2696,7 +2749,7 @@ namespace rr template Reference Array::operator[](RValue index) { - Value *element = LValue::getAddress(index.value, false); + Value *element = LValue::getElementPointer(index.value, false); return Reference(element); } @@ -2704,7 +2757,7 @@ namespace rr template Reference Array::operator[](RValue index) { - Value *element = LValue::getAddress(index.value, true); + Value *element = LValue::getElementPointer(index.value, true); return Reference(element); } diff --git a/src/Reactor/ReactorUnitTests.cpp b/src/Reactor/ReactorUnitTests.cpp index e44533e7e..a5de4f9b3 100644 --- a/src/Reactor/ReactorUnitTests.cpp +++ b/src/Reactor/ReactorUnitTests.cpp @@ -112,6 +112,65 @@ TEST(ReactorUnitTests, Uninitialized) delete routine; } +TEST(ReactorUnitTests, Unreachable) +{ + Routine *routine = nullptr; + + { + Function function; + { + Int a = function.Arg<0>(); + Int z = 4; + + Return(a + z); + + // Code beyond this point is unreachable but should not cause any + // compilation issues. + + z += a; + } + + routine = function("one"); + + if(routine) + { + int (*callable)(int) = (int(*)(int))routine->getEntry(); + int result = callable(16); + EXPECT_EQ(result, 20); + } + } + + delete routine; +} + +TEST(ReactorUnitTests, VariableAddress) +{ + Routine *routine = nullptr; + + { + Function function; + { + Int a = function.Arg<0>(); + Int z = 0; + Pointer p = &z; + *p = 4; + + Return(a + z); + } + + routine = function("one"); + + if(routine) + { + int (*callable)(int) = (int(*)(int))routine->getEntry(); + int result = callable(16); + EXPECT_EQ(result, 20); + } + } + + delete routine; +} + TEST(ReactorUnitTests, SubVectorLoadStore) { Routine *routine = nullptr; diff --git a/src/Reactor/SubzeroReactor.cpp b/src/Reactor/SubzeroReactor.cpp index fce17171a..dee4af0eb 100644 --- a/src/Reactor/SubzeroReactor.cpp +++ b/src/Reactor/SubzeroReactor.cpp @@ -649,6 +649,9 @@ namespace rr void Nucleus::setInsertBlock(BasicBlock *basicBlock) { // assert(::basicBlock->getInsts().back().getTerminatorEdges().size() >= 0 && "Previous basic block must have a terminator"); + + Variable::materializeAll(); + ::basicBlock = basicBlock; } @@ -676,24 +679,38 @@ namespace rr void Nucleus::createRetVoid() { + // Code generated after this point is unreachable, so any variables + // being read can safely return an undefined value. We have to avoid + // materializing variables after the terminator ret instruction. + Variable::killUnmaterialized(); + Ice::InstRet *ret = Ice::InstRet::create(::function); ::basicBlock->appendInst(ret); } void Nucleus::createRet(Value *v) { + // Code generated after this point is unreachable, so any variables + // being read can safely return an undefined value. We have to avoid + // materializing variables after the terminator ret instruction. + Variable::killUnmaterialized(); + Ice::InstRet *ret = Ice::InstRet::create(::function, v); ::basicBlock->appendInst(ret); } void Nucleus::createBr(BasicBlock *dest) { + Variable::materializeAll(); + auto br = Ice::InstBr::create(::function, dest); ::basicBlock->appendInst(br); } void Nucleus::createCondBr(Value *cond, BasicBlock *ifTrue, BasicBlock *ifFalse) { + Variable::materializeAll(); + auto br = Ice::InstBr::create(::function, cond, ifTrue, ifFalse); ::basicBlock->appendInst(br); }