1 // Copyright (c) 2017 Google Inc. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef SOURCE_OPT_CCP_PASS_H_ 16 #define SOURCE_OPT_CCP_PASS_H_ 17 18 #include <memory> 19 #include <unordered_map> 20 21 #include "source/opt/constants.h" 22 #include "source/opt/function.h" 23 #include "source/opt/ir_context.h" 24 #include "source/opt/mem_pass.h" 25 #include "source/opt/module.h" 26 #include "source/opt/propagator.h" 27 28 namespace spvtools { 29 namespace opt { 30 31 class CCPPass : public MemPass { 32 public: 33 CCPPass() = default; 34 name()35 const char* name() const override { return "ccp"; } 36 Status Process() override; 37 GetPreservedAnalyses()38 IRContext::Analysis GetPreservedAnalyses() override { 39 return IRContext::kAnalysisDefUse | 40 IRContext::kAnalysisInstrToBlockMapping | 41 IRContext::kAnalysisDecorations | IRContext::kAnalysisCombinators | 42 IRContext::kAnalysisCFG | IRContext::kAnalysisDominatorAnalysis | 43 IRContext::kAnalysisNameMap | IRContext::kAnalysisConstants | 44 IRContext::kAnalysisTypes; 45 } 46 47 private: 48 // Initializes the pass. 49 void Initialize(); 50 51 // Runs constant propagation on the given function |fp|. Returns true if any 52 // constants were propagated and the IR modified. 53 bool PropagateConstants(Function* fp); 54 55 // Visits a single instruction |instr|. If the instruction is a conditional 56 // branch that always jumps to the same basic block, it sets the destination 57 // block in |dest_bb|. 58 SSAPropagator::PropStatus VisitInstruction(Instruction* instr, 59 BasicBlock** dest_bb); 60 61 // Visits an OpPhi instruction |phi|. This applies the meet operator for the 62 // CCP lattice. Essentially, if all the operands in |phi| have the same 63 // constant value C, the result for |phi| gets assigned the value C. 64 SSAPropagator::PropStatus VisitPhi(Instruction* phi); 65 66 // Visits an SSA assignment instruction |instr|. If the RHS of |instr| folds 67 // into a constant value C, then the LHS of |instr| is assigned the value C in 68 // |values_|. 69 SSAPropagator::PropStatus VisitAssignment(Instruction* instr); 70 71 // Visits a branch instruction |instr|. If the branch is conditional 72 // (OpBranchConditional or OpSwitch), and the value of its selector is known, 73 // |dest_bb| will be set to the corresponding destination block. Unconditional 74 // branches always set |dest_bb| to the single destination block. 75 SSAPropagator::PropStatus VisitBranch(Instruction* instr, 76 BasicBlock** dest_bb) const; 77 78 // Replaces all operands used in |fp| with the corresponding constant values 79 // in |values_|. Returns true if any operands were replaced, and false 80 // otherwise. 81 bool ReplaceValues(); 82 83 // Marks |instr| as varying by registering a varying value for its result 84 // into the |values_| table. Returns SSAPropagator::kVarying. 85 SSAPropagator::PropStatus MarkInstructionVarying(Instruction* instr); 86 87 // Returns true if |id| is the special SSA id that corresponds to a varying 88 // value. 89 bool IsVaryingValue(uint32_t id) const; 90 91 // Constant manager for the parent IR context. Used to record new constants 92 // generated during propagation. 93 analysis::ConstantManager* const_mgr_; 94 95 // Constant value table. Each entry <id, const_decl_id> in this map 96 // represents the compile-time constant value for |id| as declared by 97 // |const_decl_id|. Each |const_decl_id| in this table is an OpConstant 98 // declaration for the current module. 99 // 100 // Additionally, this table keeps track of SSA IDs with varying values. If an 101 // SSA ID is found to have a varying value, it will have an entry in this 102 // table that maps to the special SSA id kVaryingSSAId. These values are 103 // never replaced in the IR, they are used by CCP during propagation. 104 std::unordered_map<uint32_t, uint32_t> values_; 105 106 // Propagator engine used. 107 std::unique_ptr<SSAPropagator> propagator_; 108 }; 109 110 } // namespace opt 111 } // namespace spvtools 112 113 #endif // SOURCE_OPT_CCP_PASS_H_ 114