tensorflow/compiler/jit/deadness_analysis.cc
// Common code to create AndPredicate or OrPredicate instances.
Common code to create AndPredicate or OrPredicate instances.
Common code to create AndPredicate or OrPredicate instances .
Predicate* PredicateFactory::MakeAndOrImpl(
    absl::Span<Predicate* const> operands, bool is_and) {
  Predicate::Kind pred_kind =
      is_and ? Predicate::Kind::kAnd : Predicate::Kind::kOr;
  IncrementStackDepth stack_frame(this);
  if (stack_frame.HasOverflowed()) {
    return MakeInternedAndOr(
        std::vector<Predicate*>(operands.begin(), operands.end()), pred_kind);
  }
  Predicate::Kind other_pred_kind =
      is_and ? Predicate::Kind::kOr : Predicate::Kind::kAnd;
  absl::flat_hash_set<Predicate*> simplified_ops_set;
  std::vector<Predicate*> simplified_ops;
  for (Predicate* op : operands) {
    if (!simplified_ops_set.insert(op).second) {
      continue;
    }
    if (op->kind() == pred_kind) {
      for (Predicate* subop : op->GetOperands()) {
        if (simplified_ops_set.insert(subop).second) {
          simplified_ops.push_back(subop);
        }
      }
    } else {
      simplified_ops.push_back(op);
    }
  }
  if (simplified_ops.size() == 1) {
    return simplified_ops[0];
  }
  absl::flat_hash_set<Predicate*> negated_ops;
  for (Predicate* op : simplified_ops) {
    if (negated_ops.count(op)) {
         A & ~A & ... == False
         A | ~A | ... == True
      return is_and ? MakeFalse() : MakeTrue();
    }
    Predicate* negated_op = MakeNotPredicate(op);
    if (negated_op->kind() == pred_kind) {
       Slightly more complicated case:
         (~A | ~B | ~C) & A & B & C & ... ==
         ~(A & B & C) & (A & B & C) & ... == False
         (~A & ~B & ~C) | A | B | C | ... ==
         ~(A | B | C) | (A | B | C) | ... == True
      if (absl::c_all_of(negated_op->GetOperands(), [&](Predicate* p) {
            return simplified_ops_set.contains(p);
          })) {
        return is_and ? MakeFalse() : MakeTrue();
      }
    }
    negated_ops.insert(negated_op);
  }
   Simplify {S,&,X} & ~X & ... => S & ...
  if (is_and) {
    absl::flat_hash_set<Predicate*> to_remove;
    std::vector<Predicate*> to_add;
    for (Predicate* op : simplified_ops) {
      if (op->kind() == Predicate::Kind::kAndRecurrence) {
        auto* and_rec = static_cast<AndRecurrencePredicate*>(op);
        if (negated_ops.contains(and_rec->step())) {
           Remove and_rec and ~X and insert S.  Note that checking the
           existence of ~X through negated_ops is sufficient since it makes
           sure the predicate is in the input operands.  It does not need to
           be in simplified_ops if it was already cancelled out.
          to_remove.insert(and_rec);
          to_remove.insert(MakeNotPredicate(and_rec->step()));
          to_add.push_back(and_rec->start());
        }
      }
    }
    auto it = simplified_ops.begin();
    while (it != simplified_ops.end()) {
      if (to_remove.contains(*it)) {
        it = simplified_ops.erase(it);
      } else {
        ++it;
      }
    }
    simplified_ops.insert(simplified_ops.end(), to_add.begin(), to_add.end());
  }
   If all ops contain the same subop, then factor it out thanks to the
   distributive property. Such as:
   - (A & B) | (A & C) | (A & D) => A & (B | C | D)
   - (A | B) & (A | C) & (A | D) => A | (B & C & D)
   First find any predicates contained in all subops.
  std::vector<Predicate*> common_inner_operands;
  absl::flat_hash_set<Predicate*> common_inner_operands_set;
  for (Predicate* op : simplified_ops) {
    if (op->kind() != other_pred_kind) {
      common_inner_operands.clear();
      break;
    }
    if (common_inner_operands.empty()) {
      common_inner_operands.insert(common_inner_operands.end(),
                                   op->GetOperands().begin(),
                                   op->GetOperands().end());
    } else {
      common_inner_operands.clear();
      absl::c_copy_if(op->GetOperands(),
                      std::back_inserter(common_inner_operands),
                      [&](Predicate* sub_op) {
                        return common_inner_operands_set.count(sub_op) == 1;
                      });
    }
    if (common_inner_operands.empty()) break;
    common_inner_operands_set.clear();
    common_inner_operands_set.insert(common_inner_operands.begin(),
                                     common_inner_operands.end());
  }
  if (common_inner_operands.empty()) {
    return MakeInternedAndOr(std::move(simplified_ops), pred_kind);
  }
   For all predicates that can be factored out, remove them and recreate the
   subops.
  std::vector<Predicate*> factored_ops;
  for (Predicate* op : simplified_ops) {
    std::vector<Predicate*> new_sub_op_ops;
    absl::c_copy_if(op->GetOperands(), std::back_inserter(new_sub_op_ops),
                    [&](Predicate* sub_op) {
                      return std::find(common_inner_operands.begin(),
                                       common_inner_operands.end(),
                                       sub_op) == common_inner_operands.end();
                    });
    factored_ops.push_back(MakeAndOrImpl(new_sub_op_ops, !is_and));
  }
  Predicate* new_inner_op = MakeAndOrImpl(factored_ops, is_and);
  std::vector<Predicate*> outer_ops;
  outer_ops.push_back(new_inner_op);
  outer_ops.insert(outer_ops.end(), common_inner_operands.begin(),
                   common_inner_operands.end());
  return MakeAndOrImpl(outer_ops, !is_and);
}
Predicate * PredicateFactory :: MakeAndOrImpl ( absl :: Span < Predicate * const > operands , bool is_and ) { Predicate :: Kind pred_kind = is_and ? Predicate :: Kind :: kAnd : Predicate :: Kind :: kOr ; IncrementStackDepth stack_frame ( this ) ; if ( stack_frame . HasOverflowed ( ) ) { return MakeInternedAndOr ( std :: vector < Predicate * > ( operands . begin ( ) , operands . end ( ) ) , pred_kind ) ; } Predicate :: Kind other_pred_kind = is_and ? Predicate :: Kind :: kOr : Predicate :: Kind :: kAnd ; absl :: flat_hash_set < Predicate * > simplified_ops_set ; std :: vector < Predicate * > simplified_ops ; for ( Predicate * op : operands ) { if ( ! simplified_ops_set . insert ( op ) . second ) { continue ; } if ( op -> kind ( ) == pred_kind ) { for ( Predicate * subop : op -> GetOperands ( ) ) { if ( simplified_ops_set . insert ( subop ) . second ) { simplified_ops . push_back ( subop ) ; } } } else { simplified_ops . push_back ( op ) ; } } if ( simplified_ops . size ( ) == 1 ) { return simplified_ops [ 0 ] ; } absl :: flat_hash_set < Predicate * > negated_ops ; for ( Predicate * op : simplified_ops ) { if ( negated_ops . count ( op ) ) { return is_and ? MakeFalse ( ) : MakeTrue ( ) ; } Predicate * negated_op = MakeNotPredicate ( op ) ; if ( negated_op -> kind ( ) == pred_kind ) { if ( absl :: c_all_of ( negated_op -> GetOperands ( ) , [ & ] ( Predicate * p ) { return simplified_ops_set . contains ( p ) ; } ) ) { return is_and ? MakeFalse ( ) : MakeTrue ( ) ; } } negated_ops . insert ( negated_op ) ; } if ( is_and ) { absl :: flat_hash_set < Predicate * > to_remove ; std :: vector < Predicate * > to_add ; for ( Predicate * op : simplified_ops ) { if ( op -> kind ( ) == Predicate :: Kind :: kAndRecurrence ) { auto * and_rec = static_cast < AndRecurrencePredicate * > ( op ) ; if ( negated_ops . contains ( and_rec -> step ( ) ) ) { to_remove . insert ( and_rec ) ; to_remove . insert ( MakeNotPredicate ( and_rec -> step ( ) ) ) ; to_add . push_back ( and_rec -> start ( ) ) ; } } } auto it = simplified_ops . begin ( ) ; while ( it != simplified_ops . end ( ) ) { if ( to_remove . contains ( * it ) ) { it = simplified_ops . erase ( it ) ; } else { ++ it ; } } simplified_ops . insert ( simplified_ops . end ( ) , to_add . begin ( ) , to_add . end ( ) ) ; } std :: vector < Predicate * > common_inner_operands ; absl :: flat_hash_set < Predicate * > common_inner_operands_set ; for ( Predicate * op : simplified_ops ) { if ( op -> kind ( ) != other_pred_kind ) { common_inner_operands . clear ( ) ; break ; } if ( common_inner_operands . empty ( ) ) { common_inner_operands . insert ( common_inner_operands . end ( ) , op -> GetOperands ( ) . begin ( ) , op -> GetOperands ( ) . end ( ) ) ; } else { common_inner_operands . clear ( ) ; absl :: c_copy_if ( op -> GetOperands ( ) , std :: back_inserter ( common_inner_operands ) , [ & ] ( Predicate * sub_op ) { return common_inner_operands_set . count ( sub_op ) == 1 ; } ) ; } if ( common_inner_operands . empty ( ) ) break ; common_inner_operands_set . clear ( ) ; common_inner_operands_set . insert ( common_inner_operands . begin ( ) , common_inner_operands . end ( ) ) ; } if ( common_inner_operands . empty ( ) ) { return MakeInternedAndOr ( std :: move ( simplified_ops ) , pred_kind ) ; } std :: vector < Predicate * > factored_ops ; for ( Predicate * op : simplified_ops ) { std :: vector < Predicate * > new_sub_op_ops ; absl :: c_copy_if ( op -> GetOperands ( ) , std :: back_inserter ( new_sub_op_ops ) , [ & ] ( Predicate * sub_op ) { return std :: find ( common_inner_operands . begin ( ) , common_inner_operands . end ( ) , sub_op ) == common_inner_operands . end ( ) ; } ) ; factored_ops . push_back ( MakeAndOrImpl ( new_sub_op_ops , ! is_and ) ) ; } Predicate * new_inner_op = MakeAndOrImpl ( factored_ops , is_and ) ; std :: vector < Predicate * > outer_ops ; outer_ops . push_back ( new_inner_op ) ; outer_ops . insert ( outer_ops . end ( ) , common_inner_operands . begin ( ) , common_inner_operands . end ( ) ) ; return MakeAndOrImpl ( outer_ops , ! is_and ) ; }
Common code to create AndPredicate or OrPredicate instances.
Common code to create AndPredicate or OrPredicate instances .
// Simplify A&A => A and  A|A => A. // "Inline" the operands of an inner And/Or into the parent And/Or. // Simplify "A&~A=>False" and "A|~A=>True". // Simple case: // //   A & ~A & ... == False //   A | ~A | ... == True // Slightly more complicated case: // //   (~A | ~B | ~C) & A & B & C & ... == //   ~(A & B & C) & (A & B & C) & ... == False // //   (~A & ~B & ~C) | A | B | C | ... == //   ~(A | B | C) | (A | B | C) | ... == True // Simplify {S,&,X} & ~X & ... => S & ... // Remove and_rec and ~X and insert S.  Note that checking the // existence of ~X through negated_ops is sufficient since it makes // sure the predicate is in the input operands.  It does not need to // be in simplified_ops if it was already cancelled out. // If all ops contain the same subop, then factor it out thanks to the // distributive property. Such as: // - (A & B) | (A & C) | (A & D) => A & (B | C | D) // - (A | B) & (A | C) & (A | D) => A | (B & C & D) // // First find any predicates contained in all subops. // For all predicates that can be factored out, remove them and recreate the // subops.