blob: e20f1f1a5e85e3cbbf36df67d64b78b2b3212b19 [file] [log] [blame]
// Copyright (c) 2017 Google Inc.
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// See the License for the specific language governing permissions and
// limitations under the License.
#include <cstdio>
#include <memory>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include "source/opt/function.h"
#include "source/opt/pass.h"
#include "source/opt/type_manager.h"
namespace spvtools {
namespace opt {
// Documented in optimizer.hpp
class ScalarReplacementPass : public Pass {
static const uint32_t kDefaultLimit = 100;
ScalarReplacementPass(uint32_t limit = kDefaultLimit)
: max_num_elements_(limit) {
name_[0] = '\0';
strcat(name_, "scalar-replacement=");
sprintf(&name_[strlen(name_)], "%d", max_num_elements_);
const char* name() const override { return name_; }
// Attempts to scalarize all appropriate function scope variables. Returns
// SuccessWithChange if any change is made.
Status Process() override;
IRContext::Analysis GetPreservedAnalyses() override {
return IRContext::kAnalysisDefUse |
IRContext::kAnalysisInstrToBlockMapping |
IRContext::kAnalysisDecorations | IRContext::kAnalysisCombinators |
IRContext::kAnalysisCFG | IRContext::kAnalysisNameMap |
IRContext::kAnalysisConstants | IRContext::kAnalysisTypes;
// Small container for tracking statistics about variables.
// TODO(alanbaker): Develop some useful heuristics to tune this pass.
struct VariableStats {
uint32_t num_partial_accesses;
uint32_t num_full_accesses;
// Attempts to scalarize all appropriate function scope variables in
// |function|. Returns SuccessWithChange if any changes are mode.
Status ProcessFunction(Function* function);
// Returns true if |varInst| can be scalarized.
// Examines the use chain of |varInst| to verify all uses are valid for
// scalarization.
bool CanReplaceVariable(const Instruction* varInst) const;
// Returns true if |typeInst| is an acceptable type to scalarize.
// Allows all aggregate types except runtime arrays. Additionally, checks the
// that the number of elements that would be scalarized is within bounds.
bool CheckType(const Instruction* typeInst) const;
// Returns true if all the decorations for |varInst| are acceptable for
// scalarization.
bool CheckAnnotations(const Instruction* varInst) const;
// Returns true if all the decorations for |typeInst| are acceptable for
// scalarization.
bool CheckTypeAnnotations(const Instruction* typeInst) const;
// Returns true if the uses of |inst| are acceptable for scalarization.
// Recursively checks all the uses of |inst|. For |inst| specifically, only
// allows SpvOpAccessChain, SpvOpInBoundsAccessChain, SpvOpLoad and
// SpvOpStore. Access chains must have the first index be a compile-time
// constant. Subsequent uses of access chains (including other access chains)
// are checked in a more relaxed manner.
bool CheckUses(const Instruction* inst) const;
// Helper function for the above |CheckUses|.
// This version tracks some stats about the current OpVariable. These stats
// are used to drive heuristics about when to scalarize.
bool CheckUses(const Instruction* inst, VariableStats* stats) const;
// Relaxed helper function for |CheckUses|.
bool CheckUsesRelaxed(const Instruction* inst) const;
// Transfers appropriate decorations from |source| to |replacements|.
void TransferAnnotations(const Instruction* source,
std::vector<Instruction*>* replacements);
// Scalarizes |inst| and updates its uses.
// |inst| must be an OpVariable. It is replaced with an OpVariable for each
// for element of the composite type. Uses of |inst| are updated as
// appropriate. If the replacement variables are themselves scalarizable, they
// get added to |worklist| for further processing. If any replacement
// variable ends up with no uses it is erased. Returns
// - Status::SuccessWithoutChange if the variable could not be replaced.
// - Status::SuccessWithChange if it made replacements.
// - Status::Failure if it couldn't create replacement variables.
Pass::Status ReplaceVariable(Instruction* inst,
std::queue<Instruction*>* worklist);
// Returns the underlying storage type for |inst|.
// |inst| must be an OpVariable. Returns the type that is pointed to by
// |inst|.
Instruction* GetStorageType(const Instruction* inst) const;
// Returns true if the load can be scalarized.
// |inst| must be an OpLoad. Returns true if |index| is the pointer operand of
// |inst| and the load is not from volatile memory.
bool CheckLoad(const Instruction* inst, uint32_t index) const;
// Returns true if the store can be scalarized.
// |inst| must be an OpStore. Returns true if |index| is the pointer operand
// of |inst| and the store is not to volatile memory.
bool CheckStore(const Instruction* inst, uint32_t index) const;
// Creates a variable of type |typeId| from the |index|'th element of
// |varInst|. The new variable is added to |replacements|. If the variable
// could not be created, then |nullptr| is appended to |replacements|.
void CreateVariable(uint32_t typeId, Instruction* varInst, uint32_t index,
std::vector<Instruction*>* replacements);
// Populates |replacements| with a new OpVariable for each element of |inst|.
// Returns true if the replacement variables were successfully created.
// |inst| must be an OpVariable of a composite type. New variables are
// initialized the same as the corresponding index in |inst|. |replacements|
// will contain a variable for each element of the composite with matching
// indexes (i.e. the 0'th element of |inst| is the 0'th entry of
// |replacements|).
bool CreateReplacementVariables(Instruction* inst,
std::vector<Instruction*>* replacements);
// Returns the array length for |arrayInst|.
uint64_t GetArrayLength(const Instruction* arrayInst) const;
// Returns the number of elements in |type|.
// |type| must be a vector or matrix type.
uint64_t GetNumElements(const Instruction* type) const;
// Returns true if |id| is a specialization constant.
// |id| must be registered definition.
bool IsSpecConstant(uint32_t id) const;
// Returns an id for a pointer to |id|.
uint32_t GetOrCreatePointerType(uint32_t id);
// Creates the initial value for the |index| element of |source| in |newVar|.
// If there is an initial value for |source| for element |index|, it is
// appended as an operand on |newVar|. If the initial value is OpUndef, no
// initial value is added to |newVar|.
void GetOrCreateInitialValue(Instruction* source, uint32_t index,
Instruction* newVar);
// Replaces the load to the entire composite.
// Generates a load for each replacement variable and then creates a new
// composite by combining all of the loads.
// |load| must be a load. Returns true if successful.
bool ReplaceWholeLoad(Instruction* load,
const std::vector<Instruction*>& replacements);
// Replaces the store to the entire composite.
// Generates a composite extract and store for each element in the scalarized
// variable from the original store data input. Returns true if successful.
bool ReplaceWholeStore(Instruction* store,
const std::vector<Instruction*>& replacements);
// Replaces an access chain to the composite variable with either a direct use
// of the appropriate replacement variable or another access chain with the
// replacement variable as the base and one fewer indexes. Returns true if
// successful.
bool ReplaceAccessChain(Instruction* chain,
const std::vector<Instruction*>& replacements);
// Returns a set containing the which components of the result of |inst| are
// potentially used. If the return value is |nullptr|, then every components
// is possibly used.
std::unique_ptr<std::unordered_set<int64_t>> GetUsedComponents(
Instruction* inst);
// Returns an instruction defining a null constant with type |type_id|. If
// one already exists, it is returned. Otherwise a new one is created.
// Returns |nullptr| if the new constant could not be created.
Instruction* CreateNullConstant(uint32_t type_id);
// Maps storage type to a pointer type enclosing that type.
std::unordered_map<uint32_t, uint32_t> pointee_to_pointer_;
// Maps type id to OpConstantNull for that type.
std::unordered_map<uint32_t, uint32_t> type_to_null_;
// Returns the number of elements in the variable |var_inst|.
uint64_t GetMaxLegalIndex(const Instruction* var_inst) const;
// Returns true if |length| is larger than limit on the size of the variable
// that we will be willing to split.
bool IsLargerThanSizeLimit(uint64_t length) const;
// Limit on the number of members in an object that will be replaced.
// 0 means there is no limit.
uint32_t max_num_elements_;
char name_[55];
} // namespace opt
} // namespace spvtools