| 709 | } |
| 710 | |
| 711 | void HloDataflowAnalysis::Propagate() { |
| 712 | std::queue<HloInstruction*> worklist; |
| 713 | absl::flat_hash_set<HloInstruction*> workset; |
| 714 | auto add_to_worklist = [&worklist, &workset](HloInstruction* instruction) { |
| 715 | if (workset.insert(instruction).second) { |
| 716 | worklist.push(instruction); |
| 717 | } |
| 718 | }; |
| 719 | |
| 720 | for (HloComputation* computation : module_.computations()) { |
| 721 | for (HloInstruction* instruction : computation->instructions()) { |
| 722 | add_to_worklist(instruction); |
| 723 | } |
| 724 | } |
| 725 | |
| 726 | while (!worklist.empty()) { |
| 727 | HloInstruction* instruction = worklist.front(); |
| 728 | worklist.pop(); |
| 729 | workset.erase(workset.find(instruction)); |
| 730 | |
| 731 | VLOG(3) << "Worklist top: " << instruction->name(); |
| 732 | VLOG(3) << ToString(); |
| 733 | |
| 734 | if (!UpdateInstructionValueSet(instruction)) { |
| 735 | // No change to the instruction's value set. |
| 736 | VLOG(4) << "No change."; |
| 737 | continue; |
| 738 | } |
| 739 | |
| 740 | VLOG(4) << "New value set for " << instruction->name() << ": " |
| 741 | << GetInstructionValueSet(instruction); |
| 742 | |
| 743 | // Instruction value was updated. Add users to work list if we haven't |
| 744 | // already. |
| 745 | for (HloInstruction* user : instruction->users()) { |
| 746 | add_to_worklist(user); |
| 747 | |
| 748 | // If user sequentially calls a computation, then the respective |
| 749 | // parameter(s) of the computation need to be updated. |
| 750 | if (user->opcode() == HloOpcode::kConditional) { |
| 751 | // If operand 0 is the use of instruction, then no parameters need to be |
| 752 | // updated, since that is the branch_index of the conditional. |
| 753 | // If operand n+1 is the use of instruction, then the branch_computation |
| 754 | // n's parameter need to be updated. |
| 755 | // |
| 756 | // Note that the same instruction can be used in multiple branches' |
| 757 | // operands. |
| 758 | for (int j = 0; j < user->branch_count(); ++j) { |
| 759 | if (user->operand(j + 1) == instruction) { |
| 760 | add_to_worklist( |
| 761 | user->branch_computation(j)->parameter_instruction(0)); |
| 762 | } |
| 763 | } |
| 764 | } else { |
| 765 | for (HloComputation* called_computation : user->called_computations()) { |
| 766 | const CallGraphNode& call_graph_node = |
| 767 | call_graph_->GetNode(called_computation); |
| 768 | if (call_graph_node.context() == CallContext::kSequential) { |
no test coverage detected