diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index 8995c11a45c..079e06009fd 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -1694,570 +1694,284 @@ predicate::simplify (gimple *use_or_def, bool is_use)
   (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
   */
 
-/* Store a PRED in *THIS.  */
-
-void
-predicate::push_pred (const pred_info &pred)
-{
-  pred_chain chain = vNULL;
-  chain.safe_push (pred);
-  m_preds.safe_push (chain);
-}
-
-/* Dump predicates in *THIS for STMT prepended by MSG.  */
+/* Normalize predicate PRED:
+   1) if PRED can no longer be normalized, append it to *THIS.
+   2) otherwise if PRED is of the form x != 0, follow x's definition
+      and put normalized predicates into WORK_LIST.  */
 
 void
-predicate::dump (gimple *stmt, const char *msg) const
+predicate::normalize (pred_chain *norm_chain,
+		      pred_info pred,
+		      tree_code and_or_code,
+		      pred_chain *work_list,
+		      hash_set<tree> *mark_set)
 {
-  fprintf (dump_file, "%s", msg);
-  if (stmt)
+  if (!is_neq_zero_form_p (pred))
     {
-      fputc ('\t', dump_file);
-      print_gimple_stmt (dump_file, stmt, 0);
-      fprintf (dump_file, "  is conditional on:\n");
+      if (and_or_code == BIT_IOR_EXPR)
+	push_pred (pred);
+      else
+	norm_chain->safe_push (pred);
+      return;
     }
 
-  unsigned np = m_preds.length ();
-  if (np == 0)
+  gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
+
+  if (gimple_code (def_stmt) == GIMPLE_PHI
+      && is_degenerate_phi (def_stmt, &pred))
+    /* PRED has been modified above.  */
+    work_list->safe_push (pred);
+  else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR)
     {
-      fprintf (dump_file, "\t(empty)\n");
-      return;
-    }
+      unsigned n = gimple_phi_num_args (def_stmt);
 
-  {
-    tree expr = build_pred_expr (m_preds);
-    char *str = print_generic_expr_to_str (expr);
-    fprintf (dump_file, "\t%s (expanded)\n", str);
-    free (str);
-  }
+      /* Punt for a nonzero constant.  The predicate should be one guarding
+	 the phi edge.  */
+      for (unsigned i = 0; i < n; ++i)
+	{
+	  tree op = gimple_phi_arg_def (def_stmt, i);
+	  if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
+	    {
+	      push_pred (pred);
+	      return;
+	    }
+	}
 
-  if (np > 1)
-    fprintf (dump_file, "\tOR (");
+      for (unsigned i = 0; i < n; ++i)
+	{
+	  tree op = gimple_phi_arg_def (def_stmt, i);
+	  if (integer_zerop (op))
+	    continue;
+
+	  push_to_worklist (op, work_list, mark_set);
+	}
+    }
+  else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
+    {
+      if (and_or_code == BIT_IOR_EXPR)
+	push_pred (pred);
+      else
+	norm_chain->safe_push (pred);
+    }
+  else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
+    {
+      /* Avoid splitting up bit manipulations like x & 3 or y | 1.  */
+      if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt)))
+	{
+	  /* But treat x & 3 as a condition.  */
+	  if (and_or_code == BIT_AND_EXPR)
+	    {
+	      pred_info n_pred;
+	      n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt);
+	      n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt);
+	      n_pred.cond_code = and_or_code;
+	      n_pred.invert = false;
+	      norm_chain->safe_push (n_pred);
+	    }
+	}
+      else
+	{
+	  push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
+	  push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
+	}
+    }
+  else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
+	   == tcc_comparison)
+    {
+      pred_info n_pred = get_pred_info_from_cmp (def_stmt);
+      if (and_or_code == BIT_IOR_EXPR)
+	push_pred (n_pred);
+      else
+	norm_chain->safe_push (n_pred);
+    }
   else
-    fputc ('\t', dump_file);
-  for (unsigned i = 0; i < np; i++)
     {
-      dump_pred_chain (m_preds[i]);
-      if (i < np - 1)
-	fprintf (dump_file, ", ");
-      else if (i > 0)
-	fputc (')', dump_file);
+      if (and_or_code == BIT_IOR_EXPR)
+	push_pred (pred);
+      else
+	norm_chain->safe_push (pred);
     }
-  fputc ('\n', dump_file);
 }
 
-/* Initialize USE_PREDS with the predicates of the control dependence chains
-   between the basic block DEF_BB that defines a variable of interst and
-   USE_BB that uses the variable, respectively.  */
+/* Normalize PRED and store the normalized predicates in THIS->M_PREDS.  */
 
-bool
-uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_bb,
-				 basic_block use_bb)
+void
+predicate::normalize (const pred_info &pred)
 {
-  gcc_assert (use_preds.is_empty ());
-
-  /* Set CD_ROOT to the basic block closest to USE_BB that is the control
-     equivalent of (is guarded by the same predicate as) DEF_BB that also
-     dominates USE_BB.  */
-  basic_block cd_root = def_bb;
-  while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
+  if (!is_neq_zero_form_p (pred))
     {
-      /* Find CD_ROOT's closest postdominator that's its control
-	 equivalent.  */
-      if (basic_block bb = find_control_equiv_block (cd_root))
-	if (dominated_by_p (CDI_DOMINATORS, use_bb, bb))
-	  {
-	    cd_root = bb;
-	    continue;
-	  }
-
-      break;
+      push_pred (pred);
+      return;
     }
 
-  /* Set DEP_CHAINS to the set of edges between CD_ROOT and USE_BB.
-     Each DEP_CHAINS element is a series of edges whose conditions
-     are logical conjunctions.  Together, the DEP_CHAINS vector is
-     used below to initialize an OR expression of the conjunctions.  */
-  unsigned num_calls = 0;
-  unsigned num_chains = 0;
-  auto_vec<edge> dep_chains[MAX_NUM_CHAINS];
-  auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
+  tree_code and_or_code = ERROR_MARK;
 
-  if (!compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
-				  cur_chain, &num_calls))
+  gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
+  if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
+    and_or_code = gimple_assign_rhs_code (def_stmt);
+  if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR)
     {
-      gcc_assert (num_chains == 0);
-      simple_control_dep_chain (dep_chains[0], cd_root, use_bb);
-      num_chains++;
+      if (TREE_CODE_CLASS (and_or_code) == tcc_comparison)
+	{
+	  pred_info n_pred = get_pred_info_from_cmp (def_stmt);
+	  push_pred (n_pred);
+	}
+      else
+	push_pred (pred);
+      return;
     }
 
-  if (DEBUG_PREDICATE_ANALYZER && dump_file)
+
+  pred_chain norm_chain = vNULL;
+  pred_chain work_list = vNULL;
+  work_list.safe_push (pred);
+  hash_set<tree> mark_set;
+
+  while (!work_list.is_empty ())
     {
-      fprintf (dump_file, "predicate::predicate (def_bb = %u, use_bb = %u, func_t) "
-	       "initialized from %u dep_chains:\n\t",
-	       def_bb->index, use_bb->index, num_chains);
-      dump_dep_chains (dep_chains, num_chains);
+      pred_info a_pred = work_list.pop ();
+      normalize (&norm_chain, a_pred, and_or_code, &work_list, &mark_set);
     }
 
-  /* From the set of edges computed above initialize *THIS as the OR
-     condition under which the definition in DEF_BB is used in USE_BB.
-     Each OR subexpression is represented by one element of DEP_CHAINS,
-     where each element consists of a series of AND subexpressions.  */
-  use_preds.init_from_control_deps (dep_chains, num_chains);
-  return !use_preds.is_empty ();
-}
-
-/* Release resources in *THIS.  */
+  if (and_or_code == BIT_AND_EXPR)
+    m_preds.safe_push (norm_chain);
 
-predicate::~predicate ()
-{
-  unsigned n = m_preds.length ();
-  for (unsigned i = 0; i != n; ++i)
-    m_preds[i].release ();
-  m_preds.release ();
+  work_list.release ();
 }
 
-/* Copy-assign RHS to *THIS.  */
+/* Normalize a single predicate PRED_CHAIN and append it to *THIS.  */
 
-predicate&
-predicate::operator= (const predicate &rhs)
+void
+predicate::normalize (const pred_chain &chain)
 {
-  if (this == &rhs)
-    return *this;
-
-  unsigned n = m_preds.length ();
-  for (unsigned i = 0; i != n; ++i)
-    m_preds[i].release ();
-  m_preds.release ();
+  pred_chain work_list = vNULL;
+  hash_set<tree> mark_set;
+  for (unsigned i = 0; i < chain.length (); i++)
+    {
+      work_list.safe_push (chain[i]);
+      mark_set.add (chain[i].pred_lhs);
+    }
 
-  n = rhs.m_preds.length ();
-  for (unsigned i = 0; i != n; ++i)
+  /* Normalized chain of predicates built up below.  */
+  pred_chain norm_chain = vNULL;
+  while (!work_list.is_empty ())
     {
-      const pred_chain &chain = rhs.m_preds[i];
-      m_preds.safe_push (chain.copy ());
+      pred_info pi = work_list.pop ();
+      predicate pred;
+      /* The predicate object is not modified here, only NORM_CHAIN and
+	 WORK_LIST are appended to.  */
+      pred.normalize (&norm_chain, pi, BIT_AND_EXPR, &work_list, &mark_set);
     }
 
-  return *this;
+  m_preds.safe_push (norm_chain);
+  work_list.release ();
 }
 
-/* For each use edge of PHI, compute all control dependence chains
-   and convert those to the composite predicates in M_PREDS.
-   Return true if a nonempty predicate has been obtained.  */
+/* Normalize predicate chains in THIS.  */
 
-bool
-uninit_analysis::init_from_phi_def (gphi *phi)
+void
+predicate::normalize (gimple *use_or_def, bool is_use)
 {
-  gcc_assert (m_phi_def_preds.is_empty ());
-
-  basic_block phi_bb = gimple_bb (phi);
-  /* Find the closest dominating bb to be the control dependence root.  */
-  basic_block cd_root = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
-  if (!cd_root)
-    return false;
-
-  /* Set DEF_EDGES to the edges to the PHI from the bb's that provide
-     definitions of each of the PHI operands for which M_EVAL is false.  */
-  auto_vec<edge> def_edges;
-  hash_set<gimple *> visited_phis;
-  collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis);
-
-  unsigned nedges = def_edges.length ();
-  if (nedges == 0)
-    return false;
-
-  unsigned num_chains = 0;
-  auto_vec<edge> dep_chains[MAX_NUM_CHAINS];
-  auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
-  for (unsigned i = 0; i < nedges; i++)
+  if (dump_file && dump_flags & TDF_DETAILS)
     {
-      edge e = def_edges[i];
-      unsigned num_calls = 0;
-      unsigned prev_nc = num_chains;
-      compute_control_dep_chain (cd_root, e->src, dep_chains,
-				 &num_chains, cur_chain, &num_calls);
-
-      /* Update the newly added chains with the phi operand edge.  */
-      if (EDGE_COUNT (e->src->succs) > 1)
-	{
-	  if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS)
-	    dep_chains[num_chains++] = vNULL;
-	  for (unsigned j = prev_nc; j < num_chains; j++)
-	    dep_chains[j].safe_push (e);
-	}
+      fprintf (dump_file, "Before normalization ");
+      dump (use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
     }
 
-  /* Convert control dependence chains to the predicate in *THIS under
-     which the PHI operands are defined to values for which M_EVAL is
-     false.  */
-  m_phi_def_preds.init_from_control_deps (dep_chains, num_chains);
-  return !m_phi_def_preds.is_empty ();
-}
-
-/* Compute the predicates that guard the use USE_STMT and check if
-   the incoming paths that have an empty (or possibly empty) definition
-   can be pruned.  Return true if it can be determined that the use of
-   PHI's def in USE_STMT is guarded by a predicate set that does not
-   overlap with the predicate sets of all runtime paths that do not
-   have a definition.
-
-   Return false if the use is not guarded or if it cannot be determined.
-   USE_BB is the bb of the use (for phi operand use, the bb is not the bb
-   of the phi stmt, but the source bb of the operand edge).
-
-   OPNDS is a bitmap with a bit set for each PHI operand of interest.
-
-   THIS->M_PREDS contains the (memoized) defining predicate chains of
-   a PHI.  If THIS->M_PREDS is empty, the PHI's defining predicate
-   chains are computed and stored into THIS->M_PREDS as needed.
-
-   VISITED_PHIS is a pointer set of phis being visited.  */
-
-bool
-uninit_analysis::is_use_guarded (gimple *use_stmt, basic_block use_bb,
-				 gphi *phi, unsigned opnds,
-				 hash_set<gphi *> *visited)
-{
-  if (visited->add (phi))
-    return false;
-
-  /* The basic block where the PHI is defined.  */
-  basic_block def_bb = gimple_bb (phi);
-
-  if (dominated_by_p (CDI_POST_DOMINATORS, def_bb, use_bb))
-    /* The use is not guarded.  */
-    return false;
-
-  /* Try to build the predicate expression under which the PHI flows
-     into its use.  This will be empty if the PHI is defined and used
-     in the same bb.  */
-  predicate use_preds;
-  if (!init_use_preds (use_preds, def_bb, use_bb))
-    return false;
-
-  /* Try to prune the dead incoming phi edges.  */
-  if (!overlap (phi, opnds, visited, use_preds))
+  predicate norm_preds;
+  for (unsigned i = 0; i < m_preds.length (); i++)
     {
-      if (DEBUG_PREDICATE_ANALYZER && dump_file)
-	fputs ("found predicate overlap\n", dump_file);
-
-      return true;
+      if (m_preds[i].length () != 1)
+	norm_preds.normalize (m_preds[i]);
+      else
+	norm_preds.normalize (m_preds[i][0]);
     }
 
-  /* We might be able to prove that if the control dependencies for OPNDS
-     are true, the control dependencies for USE_STMT can never be true.  */
-  if (use_cannot_happen (phi, opnds, use_preds))
-    return true;
+  *this = norm_preds;
 
-  if (m_phi_def_preds.is_empty ())
+  if (dump_file)
     {
-      /* Lazily initialize *THIS from PHI.  */
-      if (!init_from_phi_def (phi))
-	return false;
-
-      m_phi_def_preds.simplify (phi);
-      m_phi_def_preds.normalize (phi);
+      fprintf (dump_file, "After normalization ");
+      dump (use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
     }
-
-  use_preds.simplify (use_stmt, /*is_use=*/true);
-  use_preds.normalize (use_stmt, /*is_use=*/true);
-
-  /* Return true if the predicate guarding the valid definition (i.e.,
-     *THIS) is a superset of the predicate guarding the use (i.e.,
-     USE_PREDS).  */
-  if (m_phi_def_preds.superset_of (use_preds))
-    return true;
-
-  return false;
 }
 
-/* Public interface to the above. */
+/* Convert the chains of control dependence edges into a set of predicates.
+   A control dependence chain is represented by a vector edges.  DEP_CHAINS
+   points to an array of NUM_CHAINS dependence chains. One edge in
+   a dependence chain is mapped to predicate expression represented by
+   pred_info type.  One dependence chain is converted to a composite
+   predicate that is the result of AND operation of pred_info mapped to
+   each edge.  A composite predicate is represented by a vector of
+   pred_info.  Sets M_PREDS to the resulting composite predicates.  */
 
-bool
-uninit_analysis::is_use_guarded (gimple *stmt, basic_block use_bb, gphi *phi,
-				 unsigned opnds)
+void
+predicate::init_from_control_deps (const vec<edge> *dep_chains,
+				   unsigned num_chains)
 {
-  hash_set<gphi *> visited;
-  return is_use_guarded (stmt, use_bb, phi, opnds, &visited);
-}
+  gcc_assert (is_empty ());
 
-/* Normalize predicate PRED:
-   1) if PRED can no longer be normalized, append it to *THIS.
-   2) otherwise if PRED is of the form x != 0, follow x's definition
-      and put normalized predicates into WORK_LIST.  */
+  bool has_valid_pred = false;
+  if (num_chains == 0)
+    return;
 
-void
-predicate::normalize (pred_chain *norm_chain,
-		      pred_info pred,
-		      tree_code and_or_code,
-		      pred_chain *work_list,
-		      hash_set<tree> *mark_set)
-{
-  if (!is_neq_zero_form_p (pred))
+  if (num_chains >= MAX_NUM_CHAINS)
     {
-      if (and_or_code == BIT_IOR_EXPR)
-	push_pred (pred);
-      else
-	norm_chain->safe_push (pred);
+      if (dump_file)
+	fprintf (dump_file, "MAX_NUM_CHAINS exceeded: %u\n", num_chains);
       return;
     }
 
-  gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
+  /* Convert the control dependency chain into a set of predicates.  */
+  m_preds.reserve (num_chains);
 
-  if (gimple_code (def_stmt) == GIMPLE_PHI
-      && is_degenerate_phi (def_stmt, &pred))
-    /* PRED has been modified above.  */
-    work_list->safe_push (pred);
-  else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR)
+  for (unsigned i = 0; i < num_chains; i++)
     {
-      unsigned n = gimple_phi_num_args (def_stmt);
+      /* One path through the CFG represents a logical conjunction
+	 of the predicates.  */
+      const vec<edge> &path = dep_chains[i];
 
-      /* Punt for a nonzero constant.  The predicate should be one guarding
-	 the phi edge.  */
-      for (unsigned i = 0; i < n; ++i)
+      has_valid_pred = false;
+      /* The chain of predicates guarding the definition along this path.  */
+      pred_chain t_chain{ };
+      for (unsigned j = 0; j < path.length (); j++)
 	{
-	  tree op = gimple_phi_arg_def (def_stmt, i);
-	  if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
+	  edge e = path[j];
+	  basic_block guard_bb = e->src;
+	  /* Ignore empty forwarder blocks.  */
+	  if (empty_block_p (guard_bb) && single_succ_p (guard_bb))
+	    continue;
+
+	  /* An empty basic block here is likely a PHI, and is not one
+	     of the cases we handle below.  */
+	  gimple_stmt_iterator gsi = gsi_last_bb (guard_bb);
+	  if (gsi_end_p (gsi))
 	    {
-	      push_pred (pred);
-	      return;
+	      has_valid_pred = false;
+	      break;
 	    }
-	}
-
-      for (unsigned i = 0; i < n; ++i)
-	{
-	  tree op = gimple_phi_arg_def (def_stmt, i);
-	  if (integer_zerop (op))
+	  /* Get the conditional controlling the bb exit edge.  */
+	  gimple *cond_stmt = gsi_stmt (gsi);
+	  if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
+	    /* Ignore EH edge.  Can add assertion on the other edge's flag.  */
 	    continue;
-
-	  push_to_worklist (op, work_list, mark_set);
-	}
-    }
-  else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
-    {
-      if (and_or_code == BIT_IOR_EXPR)
-	push_pred (pred);
-      else
-	norm_chain->safe_push (pred);
-    }
-  else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
-    {
-      /* Avoid splitting up bit manipulations like x & 3 or y | 1.  */
-      if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt)))
-	{
-	  /* But treat x & 3 as a condition.  */
-	  if (and_or_code == BIT_AND_EXPR)
+	  /* Skip if there is essentially one succesor.  */
+	  if (EDGE_COUNT (e->src->succs) == 2)
 	    {
-	      pred_info n_pred;
-	      n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt);
-	      n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt);
-	      n_pred.cond_code = and_or_code;
-	      n_pred.invert = false;
-	      norm_chain->safe_push (n_pred);
-	    }
-	}
-      else
-	{
-	  push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
-	  push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
-	}
-    }
-  else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
-	   == tcc_comparison)
-    {
-      pred_info n_pred = get_pred_info_from_cmp (def_stmt);
-      if (and_or_code == BIT_IOR_EXPR)
-	push_pred (n_pred);
-      else
-	norm_chain->safe_push (n_pred);
-    }
-  else
-    {
-      if (and_or_code == BIT_IOR_EXPR)
-	push_pred (pred);
-      else
-	norm_chain->safe_push (pred);
-    }
-}
-
-/* Normalize PRED and store the normalized predicates in THIS->M_PREDS.  */
-
-void
-predicate::normalize (const pred_info &pred)
-{
-  if (!is_neq_zero_form_p (pred))
-    {
-      push_pred (pred);
-      return;
-    }
-
-  tree_code and_or_code = ERROR_MARK;
-
-  gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
-  if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
-    and_or_code = gimple_assign_rhs_code (def_stmt);
-  if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR)
-    {
-      if (TREE_CODE_CLASS (and_or_code) == tcc_comparison)
-	{
-	  pred_info n_pred = get_pred_info_from_cmp (def_stmt);
-	  push_pred (n_pred);
-	}
-      else
-	push_pred (pred);
-      return;
-    }
-
-
-  pred_chain norm_chain = vNULL;
-  pred_chain work_list = vNULL;
-  work_list.safe_push (pred);
-  hash_set<tree> mark_set;
-
-  while (!work_list.is_empty ())
-    {
-      pred_info a_pred = work_list.pop ();
-      normalize (&norm_chain, a_pred, and_or_code, &work_list, &mark_set);
-    }
-
-  if (and_or_code == BIT_AND_EXPR)
-    m_preds.safe_push (norm_chain);
-
-  work_list.release ();
-}
-
-/* Normalize a single predicate PRED_CHAIN and append it to *THIS.  */
-
-void
-predicate::normalize (const pred_chain &chain)
-{
-  pred_chain work_list = vNULL;
-  hash_set<tree> mark_set;
-  for (unsigned i = 0; i < chain.length (); i++)
-    {
-      work_list.safe_push (chain[i]);
-      mark_set.add (chain[i].pred_lhs);
-    }
-
-  /* Normalized chain of predicates built up below.  */
-  pred_chain norm_chain = vNULL;
-  while (!work_list.is_empty ())
-    {
-      pred_info pi = work_list.pop ();
-      predicate pred;
-      /* The predicate object is not modified here, only NORM_CHAIN and
-	 WORK_LIST are appended to.  */
-      pred.normalize (&norm_chain, pi, BIT_AND_EXPR, &work_list, &mark_set);
-    }
-
-  m_preds.safe_push (norm_chain);
-  work_list.release ();
-}
-
-/* Normalize predicate chains in THIS.  */
-
-void
-predicate::normalize (gimple *use_or_def, bool is_use)
-{
-  if (dump_file && dump_flags & TDF_DETAILS)
-    {
-      fprintf (dump_file, "Before normalization ");
-      dump (use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
-    }
-
-  predicate norm_preds;
-  for (unsigned i = 0; i < m_preds.length (); i++)
-    {
-      if (m_preds[i].length () != 1)
-	norm_preds.normalize (m_preds[i]);
-      else
-	norm_preds.normalize (m_preds[i][0]);
-    }
-
-  *this = norm_preds;
-
-  if (dump_file)
-    {
-      fprintf (dump_file, "After normalization ");
-      dump (use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
-    }
-}
-
-/* Convert the chains of control dependence edges into a set of predicates.
-   A control dependence chain is represented by a vector edges.  DEP_CHAINS
-   points to an array of NUM_CHAINS dependence chains. One edge in
-   a dependence chain is mapped to predicate expression represented by
-   pred_info type.  One dependence chain is converted to a composite
-   predicate that is the result of AND operation of pred_info mapped to
-   each edge.  A composite predicate is represented by a vector of
-   pred_info.  Sets M_PREDS to the resulting composite predicates.  */
-
-void
-predicate::init_from_control_deps (const vec<edge> *dep_chains,
-				   unsigned num_chains)
-{
-  gcc_assert (is_empty ());
-
-  bool has_valid_pred = false;
-  if (num_chains == 0)
-    return;
-
-  if (num_chains >= MAX_NUM_CHAINS)
-    {
-      if (dump_file)
-	fprintf (dump_file, "MAX_NUM_CHAINS exceeded: %u\n", num_chains);
-      return;
-    }
-
-  /* Convert the control dependency chain into a set of predicates.  */
-  m_preds.reserve (num_chains);
-
-  for (unsigned i = 0; i < num_chains; i++)
-    {
-      /* One path through the CFG represents a logical conjunction
-	 of the predicates.  */
-      const vec<edge> &path = dep_chains[i];
-
-      has_valid_pred = false;
-      /* The chain of predicates guarding the definition along this path.  */
-      pred_chain t_chain{ };
-      for (unsigned j = 0; j < path.length (); j++)
-	{
-	  edge e = path[j];
-	  basic_block guard_bb = e->src;
-	  /* Ignore empty forwarder blocks.  */
-	  if (empty_block_p (guard_bb) && single_succ_p (guard_bb))
-	    continue;
-
-	  /* An empty basic block here is likely a PHI, and is not one
-	     of the cases we handle below.  */
-	  gimple_stmt_iterator gsi = gsi_last_bb (guard_bb);
-	  if (gsi_end_p (gsi))
-	    {
-	      has_valid_pred = false;
-	      break;
-	    }
-	  /* Get the conditional controlling the bb exit edge.  */
-	  gimple *cond_stmt = gsi_stmt (gsi);
-	  if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
-	    /* Ignore EH edge.  Can add assertion on the other edge's flag.  */
-	    continue;
-	  /* Skip if there is essentially one succesor.  */
-	  if (EDGE_COUNT (e->src->succs) == 2)
-	    {
-	      edge e1;
-	      edge_iterator ei1;
-	      bool skip = false;
-
-	      FOR_EACH_EDGE (e1, ei1, e->src->succs)
-		{
-		  if (EDGE_COUNT (e1->dest->succs) == 0)
-		    {
-		      skip = true;
-		      break;
-		    }
-		}
-	      if (skip)
-		continue;
+	      edge e1;
+	      edge_iterator ei1;
+	      bool skip = false;
+
+	      FOR_EACH_EDGE (e1, ei1, e->src->succs)
+		{
+		  if (EDGE_COUNT (e1->dest->succs) == 0)
+		    {
+		      skip = true;
+		      break;
+		    }
+		}
+	      if (skip)
+		continue;
 	    }
 	  if (gimple_code (cond_stmt) == GIMPLE_COND)
 	    {
@@ -2353,3 +2067,289 @@ predicate::init_from_control_deps (const vec<edge> *dep_chains,
     /* Clear M_PREDS to indicate failure.  */
     m_preds.release ();
 }
+/* Store a PRED in *THIS.  */
+
+void
+predicate::push_pred (const pred_info &pred)
+{
+  pred_chain chain = vNULL;
+  chain.safe_push (pred);
+  m_preds.safe_push (chain);
+}
+
+/* Dump predicates in *THIS for STMT prepended by MSG.  */
+
+void
+predicate::dump (gimple *stmt, const char *msg) const
+{
+  fprintf (dump_file, "%s", msg);
+  if (stmt)
+    {
+      fputc ('\t', dump_file);
+      print_gimple_stmt (dump_file, stmt, 0);
+      fprintf (dump_file, "  is conditional on:\n");
+    }
+
+  unsigned np = m_preds.length ();
+  if (np == 0)
+    {
+      fprintf (dump_file, "\t(empty)\n");
+      return;
+    }
+
+  {
+    tree expr = build_pred_expr (m_preds);
+    char *str = print_generic_expr_to_str (expr);
+    fprintf (dump_file, "\t%s (expanded)\n", str);
+    free (str);
+  }
+
+  if (np > 1)
+    fprintf (dump_file, "\tOR (");
+  else
+    fputc ('\t', dump_file);
+  for (unsigned i = 0; i < np; i++)
+    {
+      dump_pred_chain (m_preds[i]);
+      if (i < np - 1)
+	fprintf (dump_file, ", ");
+      else if (i > 0)
+	fputc (')', dump_file);
+    }
+  fputc ('\n', dump_file);
+}
+
+/* Initialize USE_PREDS with the predicates of the control dependence chains
+   between the basic block DEF_BB that defines a variable of interst and
+   USE_BB that uses the variable, respectively.  */
+
+bool
+uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_bb,
+				 basic_block use_bb)
+{
+  gcc_assert (use_preds.is_empty ());
+
+  /* Set CD_ROOT to the basic block closest to USE_BB that is the control
+     equivalent of (is guarded by the same predicate as) DEF_BB that also
+     dominates USE_BB.  */
+  basic_block cd_root = def_bb;
+  while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
+    {
+      /* Find CD_ROOT's closest postdominator that's its control
+	 equivalent.  */
+      if (basic_block bb = find_control_equiv_block (cd_root))
+	if (dominated_by_p (CDI_DOMINATORS, use_bb, bb))
+	  {
+	    cd_root = bb;
+	    continue;
+	  }
+
+      break;
+    }
+
+  /* Set DEP_CHAINS to the set of edges between CD_ROOT and USE_BB.
+     Each DEP_CHAINS element is a series of edges whose conditions
+     are logical conjunctions.  Together, the DEP_CHAINS vector is
+     used below to initialize an OR expression of the conjunctions.  */
+  unsigned num_calls = 0;
+  unsigned num_chains = 0;
+  auto_vec<edge> dep_chains[MAX_NUM_CHAINS];
+  auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
+
+  if (!compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
+				  cur_chain, &num_calls))
+    {
+      gcc_assert (num_chains == 0);
+      simple_control_dep_chain (dep_chains[0], cd_root, use_bb);
+      num_chains++;
+    }
+
+  if (DEBUG_PREDICATE_ANALYZER && dump_file)
+    {
+      fprintf (dump_file, "predicate::predicate (def_bb = %u, use_bb = %u, func_t) "
+	       "initialized from %u dep_chains:\n\t",
+	       def_bb->index, use_bb->index, num_chains);
+      dump_dep_chains (dep_chains, num_chains);
+    }
+
+  /* From the set of edges computed above initialize *THIS as the OR
+     condition under which the definition in DEF_BB is used in USE_BB.
+     Each OR subexpression is represented by one element of DEP_CHAINS,
+     where each element consists of a series of AND subexpressions.  */
+  use_preds.init_from_control_deps (dep_chains, num_chains);
+  return !use_preds.is_empty ();
+}
+
+/* Release resources in *THIS.  */
+
+predicate::~predicate ()
+{
+  unsigned n = m_preds.length ();
+  for (unsigned i = 0; i != n; ++i)
+    m_preds[i].release ();
+  m_preds.release ();
+}
+
+/* Copy-assign RHS to *THIS.  */
+
+predicate&
+predicate::operator= (const predicate &rhs)
+{
+  if (this == &rhs)
+    return *this;
+
+  unsigned n = m_preds.length ();
+  for (unsigned i = 0; i != n; ++i)
+    m_preds[i].release ();
+  m_preds.release ();
+
+  n = rhs.m_preds.length ();
+  for (unsigned i = 0; i != n; ++i)
+    {
+      const pred_chain &chain = rhs.m_preds[i];
+      m_preds.safe_push (chain.copy ());
+    }
+
+  return *this;
+}
+
+/* For each use edge of PHI, compute all control dependence chains
+   and convert those to the composite predicates in M_PREDS.
+   Return true if a nonempty predicate has been obtained.  */
+
+bool
+uninit_analysis::init_from_phi_def (gphi *phi)
+{
+  gcc_assert (m_phi_def_preds.is_empty ());
+
+  basic_block phi_bb = gimple_bb (phi);
+  /* Find the closest dominating bb to be the control dependence root.  */
+  basic_block cd_root = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
+  if (!cd_root)
+    return false;
+
+  /* Set DEF_EDGES to the edges to the PHI from the bb's that provide
+     definitions of each of the PHI operands for which M_EVAL is false.  */
+  auto_vec<edge> def_edges;
+  hash_set<gimple *> visited_phis;
+  collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis);
+
+  unsigned nedges = def_edges.length ();
+  if (nedges == 0)
+    return false;
+
+  unsigned num_chains = 0;
+  auto_vec<edge> dep_chains[MAX_NUM_CHAINS];
+  auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
+  for (unsigned i = 0; i < nedges; i++)
+    {
+      edge e = def_edges[i];
+      unsigned num_calls = 0;
+      unsigned prev_nc = num_chains;
+      compute_control_dep_chain (cd_root, e->src, dep_chains,
+				 &num_chains, cur_chain, &num_calls);
+
+      /* Update the newly added chains with the phi operand edge.  */
+      if (EDGE_COUNT (e->src->succs) > 1)
+	{
+	  if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS)
+	    dep_chains[num_chains++] = vNULL;
+	  for (unsigned j = prev_nc; j < num_chains; j++)
+	    dep_chains[j].safe_push (e);
+	}
+    }
+
+  /* Convert control dependence chains to the predicate in *THIS under
+     which the PHI operands are defined to values for which M_EVAL is
+     false.  */
+  m_phi_def_preds.init_from_control_deps (dep_chains, num_chains);
+  return !m_phi_def_preds.is_empty ();
+}
+
+/* Compute the predicates that guard the use USE_STMT and check if
+   the incoming paths that have an empty (or possibly empty) definition
+   can be pruned.  Return true if it can be determined that the use of
+   PHI's def in USE_STMT is guarded by a predicate set that does not
+   overlap with the predicate sets of all runtime paths that do not
+   have a definition.
+
+   Return false if the use is not guarded or if it cannot be determined.
+   USE_BB is the bb of the use (for phi operand use, the bb is not the bb
+   of the phi stmt, but the source bb of the operand edge).
+
+   OPNDS is a bitmap with a bit set for each PHI operand of interest.
+
+   THIS->M_PREDS contains the (memoized) defining predicate chains of
+   a PHI.  If THIS->M_PREDS is empty, the PHI's defining predicate
+   chains are computed and stored into THIS->M_PREDS as needed.
+
+   VISITED_PHIS is a pointer set of phis being visited.  */
+
+bool
+uninit_analysis::is_use_guarded (gimple *use_stmt, basic_block use_bb,
+				 gphi *phi, unsigned opnds,
+				 hash_set<gphi *> *visited)
+{
+  if (visited->add (phi))
+    return false;
+
+  /* The basic block where the PHI is defined.  */
+  basic_block def_bb = gimple_bb (phi);
+
+  if (dominated_by_p (CDI_POST_DOMINATORS, def_bb, use_bb))
+    /* The use is not guarded.  */
+    return false;
+
+  /* Try to build the predicate expression under which the PHI flows
+     into its use.  This will be empty if the PHI is defined and used
+     in the same bb.  */
+  predicate use_preds;
+  if (!init_use_preds (use_preds, def_bb, use_bb))
+    return false;
+
+  /* Try to prune the dead incoming phi edges.  */
+  if (!overlap (phi, opnds, visited, use_preds))
+    {
+      if (DEBUG_PREDICATE_ANALYZER && dump_file)
+	fputs ("found predicate overlap\n", dump_file);
+
+      return true;
+    }
+
+  /* We might be able to prove that if the control dependencies for OPNDS
+     are true, the control dependencies for USE_STMT can never be true.  */
+  if (use_cannot_happen (phi, opnds, use_preds))
+    return true;
+
+  if (m_phi_def_preds.is_empty ())
+    {
+      /* Lazily initialize *THIS from PHI.  */
+      if (!init_from_phi_def (phi))
+	return false;
+
+      m_phi_def_preds.simplify (phi);
+      m_phi_def_preds.normalize (phi);
+    }
+
+  use_preds.simplify (use_stmt, /*is_use=*/true);
+  use_preds.normalize (use_stmt, /*is_use=*/true);
+
+  /* Return true if the predicate guarding the valid definition (i.e.,
+     *THIS) is a superset of the predicate guarding the use (i.e.,
+     USE_PREDS).  */
+  if (m_phi_def_preds.superset_of (use_preds))
+    return true;
+
+  return false;
+}
+
+/* Public interface to the above. */
+
+bool
+uninit_analysis::is_use_guarded (gimple *stmt, basic_block use_bb, gphi *phi,
+				 unsigned opnds)
+{
+  hash_set<gphi *> visited;
+  return is_use_guarded (stmt, use_bb, phi, opnds, &visited);
+}
+
