| 1096 | } // namespace |
| 1097 | |
| 1098 | Status DeadnessAnalysisImpl::HandleMerge(Node* n, |
| 1099 | std::vector<bool>* should_revisit, |
| 1100 | bool use_optimistic_mode) { |
| 1101 | // Merge ignores deadness of its control inputs. A merge that isn't the |
| 1102 | // target of a backedge has is alive iff any of its data inputs are. The |
| 1103 | // liveness of a merge that is the target of a backedge can sometimes be |
| 1104 | // represented using a AndRecurrencePredicate. If neither apply, we represent |
| 1105 | // the liveness of the merge symbolically. |
| 1106 | |
| 1107 | bool has_unvisited_backedge = false; |
| 1108 | for (const Edge* e : n->in_edges()) { |
| 1109 | if (!e->IsControlEdge() && e->src()->IsNextIteration()) { |
| 1110 | has_unvisited_backedge |= !predicate_map_.count(InputEdgeToTensorId(e)); |
| 1111 | } |
| 1112 | } |
| 1113 | |
| 1114 | auto it = predicate_map_.find(TensorId(n->name(), 0)); |
| 1115 | if (it == predicate_map_.end()) { |
| 1116 | if (has_unvisited_backedge) { |
| 1117 | // We're visiting this merge for the first time and it has an unvisited |
| 1118 | // backedge. |
| 1119 | Predicate* input_data_pred; |
| 1120 | if (use_optimistic_mode) { |
| 1121 | // In the optimistic mode, we use the first-seen Merge node per |
| 1122 | // frame as the representative Merge node. It is just convenient and |
| 1123 | // does not affect the result after pattern-matching into the |
| 1124 | // AndRecurrence form. |
| 1125 | absl::string_view frame_name = control_flow_info_[n->id()].frame_name; |
| 1126 | auto insert_result = frame_to_merge_node_.insert({frame_name, n}); |
| 1127 | Node* representative = insert_result.first->second; |
| 1128 | TF_RETURN_IF_ERROR(predicate_factory_.MakeSymbolPredicate( |
| 1129 | representative, /*output_idx=*/0, /*must_be_true=*/false, |
| 1130 | &input_data_pred)); |
| 1131 | } else { |
| 1132 | TF_RETURN_IF_ERROR(predicate_factory_.MakeSymbolPredicate( |
| 1133 | n, /*output_idx=*/0, /*must_be_true=*/false, &input_data_pred)); |
| 1134 | } |
| 1135 | |
| 1136 | SetPredicate(n, {0, 1, Graph::kControlSlot}, input_data_pred, |
| 1137 | should_revisit); |
| 1138 | return Status::OK(); |
| 1139 | } |
| 1140 | |
| 1141 | std::vector<Predicate*> input_preds; |
| 1142 | TF_RETURN_IF_ERROR(GetInputPreds(n, EdgeKind::kDataOnly, &input_preds)); |
| 1143 | |
| 1144 | // We're visiting this merge for the first time and it is an acyclic merge. |
| 1145 | Predicate* input_data_pred = |
| 1146 | predicate_factory_.MakeOrPredicate(input_preds); |
| 1147 | SetPredicate(n, {0, 1, Graph::kControlSlot}, input_data_pred, |
| 1148 | should_revisit); |
| 1149 | return Status::OK(); |
| 1150 | } |
| 1151 | |
| 1152 | if (it->second->kind() == Predicate::Kind::kSymbol) { |
| 1153 | // Last time we visited this merge we only got a symbolic predicate because |
| 1154 | // of an unvisited backedge. Try to pattern match the predicate expression |
| 1155 | // for that backedge (which should be visited now) into an and recurrence |
nothing calls this directly
no test coverage detected