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; 44 } 45 46 private: 47 // Initializes the pass. 48 void Initialize(); 49 50 // Runs constant propagation on the given function |fp|. Returns true if any 51 // constants were propagated and the IR modified. 52 bool PropagateConstants(Function* fp); 53 54 // Visits a single instruction |instr|. If the instruction is a conditional 55 // branch that always jumps to the same basic block, it sets the destination 56 // block in |dest_bb|. 57 SSAPropagator::PropStatus VisitInstruction(Instruction* instr, 58 BasicBlock** dest_bb); 59 60 // Visits an OpPhi instruction |phi|. This applies the meet operator for the 61 // CCP lattice. Essentially, if all the operands in |phi| have the same 62 // constant value C, the result for |phi| gets assigned the value C. 63 SSAPropagator::PropStatus VisitPhi(Instruction* phi); 64 65 // Visits an SSA assignment instruction |instr|. If the RHS of |instr| folds 66 // into a constant value C, then the LHS of |instr| is assigned the value C in 67 // |values_|. 68 SSAPropagator::PropStatus VisitAssignment(Instruction* instr); 69 70 // Visits a branch instruction |instr|. If the branch is conditional 71 // (OpBranchConditional or OpSwitch), and the value of its selector is known, 72 // |dest_bb| will be set to the corresponding destination block. Unconditional 73 // branches always set |dest_bb| to the single destination block. 74 SSAPropagator::PropStatus VisitBranch(Instruction* instr, 75 BasicBlock** dest_bb) const; 76 77 // Replaces all operands used in |fp| with the corresponding constant values 78 // in |values_|. Returns true if any operands were replaced, and false 79 // otherwise. 80 bool ReplaceValues(); 81 82 // Marks |instr| as varying by registering a varying value for its result 83 // into the |values_| table. Returns SSAPropagator::kVarying. 84 SSAPropagator::PropStatus MarkInstructionVarying(Instruction* instr); 85 86 // Returns true if |id| is the special SSA id that corresponds to a varying 87 // value. 88 bool IsVaryingValue(uint32_t id) const; 89 90 // Constant manager for the parent IR context. Used to record new constants 91 // generated during propagation. 92 analysis::ConstantManager* const_mgr_; 93 94 // Constant value table. Each entry <id, const_decl_id> in this map 95 // represents the compile-time constant value for |id| as declared by 96 // |const_decl_id|. Each |const_decl_id| in this table is an OpConstant 97 // declaration for the current module. 98 // 99 // Additionally, this table keeps track of SSA IDs with varying values. If an 100 // SSA ID is found to have a varying value, it will have an entry in this 101 // table that maps to the special SSA id kVaryingSSAId. These values are 102 // never replaced in the IR, they are used by CCP during propagation. 103 std::unordered_map<uint32_t, uint32_t> values_; 104 105 // Propagator engine used. 106 std::unique_ptr<SSAPropagator> propagator_; 107 }; 108 109 } // namespace opt 110 } // namespace spvtools 111 112 #endif // SOURCE_OPT_CCP_PASS_H_ 113