1 /* Copyright 2018 The TensorFlow Authors. All Rights Reserved. 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 16 #ifndef TENSORFLOW_COMPILER_XLA_SERVICE_HLO_LIVENESS_ANALYSIS_H_ 17 #define TENSORFLOW_COMPILER_XLA_SERVICE_HLO_LIVENESS_ANALYSIS_H_ 18 19 #include <unordered_map> 20 21 #include "tensorflow/compiler/xla/service/call_graph.h" 22 #include "tensorflow/compiler/xla/service/hlo_instruction.h" 23 #include "tensorflow/compiler/xla/service/hlo_module.h" 24 #include "tensorflow/compiler/xla/service/hlo_value.h" 25 #include "tensorflow/compiler/xla/shape_tree.h" 26 #include "tensorflow/compiler/xla/shape_util.h" 27 #include "tensorflow/compiler/xla/status.h" 28 #include "tensorflow/compiler/xla/statusor.h" 29 30 namespace xla { 31 32 // Analysis which identifies all live {HloInstruction, ShapeIndex} pairs in 33 // an HLO module. 34 // 35 // HloLivenessAnalysis marks the shape index of each live output of each 36 // instruction in the module, by propagating live shape index information 37 // from an instruction to its called computations and operands. 38 class HloLivenessAnalysis { 39 public: 40 // Maps from an HloInstruction to its live/dead output shape indices. 41 using HloIndexMap = 42 std::unordered_map<const HloInstruction*, ShapeTree<bool>>; 43 44 // Runs liveness analysis on 'module'. Returns HloLivenessAnalysis object 45 // which exports liveness for each {HloInstruction, ShapeIndex} in 'module'. 46 static StatusOr<std::unique_ptr<HloLivenessAnalysis>> Run( 47 const HloModule& module); 48 49 // Returns true if output of 'instruction' at 'shape_index' is live. 50 // Returns false otherwise. 51 bool IsLive(const HloInstruction* instruction, 52 const ShapeIndex& shape_index) const; 53 54 private: 55 HloLivenessAnalysis(const HloModule& module); 56 57 void RunAnalysis(); 58 59 const HloModule& module_; 60 std::unique_ptr<CallGraph> call_graph_; 61 HloIndexMap live_index_map_; 62 }; 63 64 } // namespace xla 65 66 #endif // TENSORFLOW_COMPILER_XLA_SERVICE_HLO_LIVENESS_ANALYSIS_H_ 67