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_REDUNDANCY_ELIMINATION_H_ 16 #define SOURCE_OPT_REDUNDANCY_ELIMINATION_H_ 17 18 #include <map> 19 20 #include "source/opt/ir_context.h" 21 #include "source/opt/local_redundancy_elimination.h" 22 #include "source/opt/pass.h" 23 #include "source/opt/value_number_table.h" 24 25 namespace spvtools { 26 namespace opt { 27 28 // This pass implements total redundancy elimination. This is the same as 29 // local redundancy elimination except it looks across basic block boundaries. 30 // An instruction, inst, is totally redundant if there is another instruction 31 // that dominates inst, and also computes the same value. 32 class RedundancyEliminationPass : public LocalRedundancyEliminationPass { 33 public: name()34 const char* name() const override { return "redundancy-elimination"; } 35 Status Process() override; 36 37 protected: 38 // Removes for all total redundancies in the function starting at |bb|. 39 // 40 // |vnTable| must have computed a value number for every result id defined 41 // in the function containing |bb|. 42 // 43 // |value_to_ids| is a map from value number to ids. If {vn, id} is in 44 // |value_to_ids| then vn is the value number of id, and the defintion of id 45 // dominates |bb|. 46 // 47 // Returns true if at least one instruction is deleted. 48 bool EliminateRedundanciesFrom(DominatorTreeNode* bb, 49 const ValueNumberTable& vnTable, 50 std::map<uint32_t, uint32_t> value_to_ids); 51 }; 52 53 } // namespace opt 54 } // namespace spvtools 55 56 #endif // SOURCE_OPT_REDUNDANCY_ELIMINATION_H_ 57