ssa_rewrite_pass.cpp | Explore in Territory

// Copyright (c) 2018 Google LLC.
//
// 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
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// This file implements the SSA rewriting algorithm proposed in
//
//      Simple and Efficient Construction of Static Single Assignment Form.
//      Braun M., Buchwald S., Hack S., Leißa R., Mallon C., Zwinkau A. (2013)
//      In: Jhala R., De Bosschere K. (eds)
//      Compiler Construction. CC 2013.
//      Lecture Notes in Computer Science, vol 7791.
//      Springer, Berlin, Heidelberg
//
//      https://link.springer.com/chapter/10.1007/978-3-642-37051-9_6
//
// In contrast to common eager algorithms based on dominance and dominance
// frontier information, this algorithm works backwards from load operations.
//
// When a target variable is loaded, it queries the variable's reaching
// definition.  If the reaching definition is unknown at the current location,
// it searches backwards in the CFG, inserting Phi instructions at join points
// in the CFG along the way until it finds the desired store instruction.
//
// The algorithm avoids repeated lookups using memoization.
//
// For reducible CFGs, which are a superset of the structured CFGs in SPIRV,
// this algorithm is proven to produce minimal SSA.  That is, it inserts the
// minimal number of Phi instructions required to ensure the SSA property, but
// some Phi instructions may be dead
// (https://en.wikipedia.org/wiki/Static_single_assignment_form).

#include "source/opt/ssa_rewrite_pass.h"

#include <memory>
#include <sstream>

#include "source/opcode.h"
#include "source/opt/cfg.h"
#include "source/opt/mem_pass.h"
#include "source/opt/types.h"

// Debug logging (0: Off, 1-N: Verbosity level).  Replace this with the
// implementation done for
// https://github.com/KhronosGroup/SPIRV-Tools/issues/1351
// #define SSA_REWRITE_DEBUGGING_LEVEL 3

#ifdef SSA_REWRITE_DEBUGGING_LEVEL
#include <ostream>
#else
#define SSA_REWRITE_DEBUGGING_LEVEL …
#endif

namespace spvtools {
namespace opt {
namespace {
constexpr uint32_t kStoreValIdInIdx = …;
constexpr uint32_t kVariableInitIdInIdx = …;
}  // namespace

std::string SSARewriter::PhiCandidate::PrettyPrint(const CFG* cfg) const { … }

SSARewriter::PhiCandidate& SSARewriter::CreatePhiCandidate(uint32_t var_id,
                                                           BasicBlock* bb) { … }

void SSARewriter::ReplacePhiUsersWith(const PhiCandidate& phi_to_remove,
                                      uint32_t repl_id) { … }

uint32_t SSARewriter::TryRemoveTrivialPhi(PhiCandidate* phi_candidate) { … }

uint32_t SSARewriter::AddPhiOperands(PhiCandidate* phi_candidate) { … }

uint32_t SSARewriter::GetValueAtBlock(uint32_t var_id, BasicBlock* bb) { … }

uint32_t SSARewriter::GetReachingDef(uint32_t var_id, BasicBlock* bb) { … }

void SSARewriter::SealBlock(BasicBlock* bb) { … }

void SSARewriter::ProcessStore(Instruction* inst, BasicBlock* bb) { … }

bool SSARewriter::ProcessLoad(Instruction* inst, BasicBlock* bb) { … }

void SSARewriter::PrintPhiCandidates() const { … }

void SSARewriter::PrintReplacementTable() const { … }

bool SSARewriter::GenerateSSAReplacements(BasicBlock* bb) { … }

uint32_t SSARewriter::GetReplacement(std::pair<uint32_t, uint32_t> repl) { … }

uint32_t SSARewriter::GetPhiArgument(const PhiCandidate* phi_candidate,
                                     uint32_t ix) { … }

bool SSARewriter::ApplyReplacements() { … }

void SSARewriter::FinalizePhiCandidate(PhiCandidate* phi_candidate) { … }

void SSARewriter::FinalizePhiCandidates() { … }

Pass::Status SSARewriter::RewriteFunctionIntoSSA(Function* fp) { … }

Pass::Status SSARewritePass::Process() { … }

}  // namespace opt
}  // namespace spvtools
chromium/third_party/spirv-tools/src/source/opt/ssa_rewrite_pass.cpp
