diff --git a/gcc/ipa-param-manipulation.cc b/gcc/ipa-param-manipulation.cc
index a0e4098a3f1..8d78ef57c12 100644
--- a/gcc/ipa-param-manipulation.cc
+++ b/gcc/ipa-param-manipulation.cc
@@ -18,6 +18,7 @@ You should have received a copy of the GNU General Public License
 along with GCC; see the file COPYING3.  If not see
 <http://www.gnu.org/licenses/>.  */
 
+#define INCLUDE_ALGORITHM
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
@@ -1000,6 +1001,7 @@ ipa_param_body_adjustments::register_replacement (tree base,
   psr.dummy = NULL_TREE;
   psr.unit_offset = unit_offset;
   m_replacements.safe_push (psr);
+  m_sorted_replacements_p = false;
 }
 
 /* Register that REPLACEMENT should replace parameter described in APM.  */
@@ -1015,6 +1017,36 @@ ipa_param_body_adjustments::register_replacement (ipa_adjusted_param *apm,
 			replacement);
 }
 
+/* Comparator to qsort ipa_param_body_adjustments::m_replacements.  */
+
+static int
+compare_param_body_replacement (const void *va, const void *vb)
+{
+  const ipa_param_body_replacement *a = (const ipa_param_body_replacement *) va;
+  const ipa_param_body_replacement *b = (const ipa_param_body_replacement *) vb;
+
+  if (DECL_UID (a->base) < DECL_UID (b->base))
+    return -1;
+  if (DECL_UID (a->base) > DECL_UID (b->base))
+    return 1;
+  if (a->unit_offset < b->unit_offset)
+    return -1;
+  if (a->unit_offset > b->unit_offset)
+    return 1;
+  return 0;
+}
+
+/* Sort m_replacements and set m_sorted_replacements_p to true.  */
+
+void
+ipa_param_body_adjustments::sort_replacements ()
+{
+  if (m_sorted_replacements_p)
+    return;
+  m_replacements.qsort (compare_param_body_replacement);
+  m_sorted_replacements_p = true;
+}
+
 /* Copy or not, as appropriate given m_id and decl context, a pre-existing
    PARM_DECL T so that it can be included in the parameters of the modified
    function.  */
@@ -1426,6 +1458,7 @@ ipa_param_body_adjustments::common_initialization (tree old_fndecl,
 	    }
 	}
     }
+  sort_replacements ();
 
   if (tree_map)
     {
@@ -1503,7 +1536,7 @@ ipa_param_body_adjustments
     m_dead_stmt_debug_equiv (), m_fndecl (fndecl), m_id (NULL), m_oparms (),
     m_new_decls (), m_new_types (), m_replacements (),
     m_split_agg_csts_inits (), m_removed_decls (), m_removed_map (),
-    m_method2func (false)
+    m_method2func (false), m_sorted_replacements_p (true)
 {
   common_initialization (fndecl, NULL, NULL);
 }
@@ -1521,7 +1554,7 @@ ipa_param_body_adjustments
     m_dead_ssa_debug_equiv (), m_dead_stmt_debug_equiv (), m_fndecl (fndecl),
     m_id (NULL), m_oparms (), m_new_decls (), m_new_types (), m_replacements (),
     m_split_agg_csts_inits (), m_removed_decls (), m_removed_map (),
-    m_method2func (false)
+    m_method2func (false), m_sorted_replacements_p (true)
 {
   common_initialization (fndecl, NULL, NULL);
 }
@@ -1545,7 +1578,7 @@ ipa_param_body_adjustments
     m_dead_ssa_debug_equiv (), m_dead_stmt_debug_equiv (), m_fndecl (fndecl),
     m_id (id), m_oparms (), m_new_decls (), m_new_types (), m_replacements (),
     m_split_agg_csts_inits (), m_removed_decls (), m_removed_map (),
-    m_method2func (false)
+    m_method2func (false), m_sorted_replacements_p (true)
 {
   common_initialization (old_fndecl, vars, tree_map);
 }
@@ -1616,16 +1649,54 @@ ipa_param_body_replacement *
 ipa_param_body_adjustments::lookup_replacement_1 (tree base,
 						  unsigned unit_offset)
 {
-  unsigned int len = m_replacements.length ();
-  for (unsigned i = 0; i < len; i++)
-    {
-      ipa_param_body_replacement *pbr = &m_replacements[i];
+  gcc_assert (m_sorted_replacements_p);
+  ipa_param_body_replacement key;
+  key.base = base;
+  key.unit_offset = unit_offset;
+  ipa_param_body_replacement *res
+    = std::lower_bound (m_replacements.begin (), m_replacements.end (), key,
+			[] (const ipa_param_body_replacement &elt,
+			    const ipa_param_body_replacement &val)
+			{
+			  if (DECL_UID (elt.base) < DECL_UID (val.base))
+			    return true;
+			  if (DECL_UID (elt.base) > DECL_UID (val.base))
+			    return false;
+			  if (elt.unit_offset < val.unit_offset)
+			    return true;
+			  return false;
+			});
 
-      if (pbr->base == base
-	  && (pbr->unit_offset == unit_offset))
-	return pbr;
-    }
-  return NULL;
+  if (res == m_replacements.end ()
+      || res->base != base
+      || res->unit_offset != unit_offset)
+    return NULL;
+  return res;
+}
+
+/* Find the first replacement for BASE among m_replacements and return pointer
+   to it, or NULL if there is none.  */
+
+ipa_param_body_replacement *
+ipa_param_body_adjustments::lookup_first_base_replacement (tree base)
+{
+  gcc_assert (m_sorted_replacements_p);
+  ipa_param_body_replacement key;
+  key.base = base;
+  ipa_param_body_replacement *res
+    = std::lower_bound (m_replacements.begin (), m_replacements.end (), key,
+			[] (const ipa_param_body_replacement &elt,
+			    const ipa_param_body_replacement &val)
+			{
+			  if (DECL_UID (elt.base) < DECL_UID (val.base))
+			    return true;
+			  return false;
+			});
+
+  if (res == m_replacements.end ()
+      || res->base != base)
+    return NULL;
+  return res;
 }
 
 /* Given BASE and UNIT_OFFSET, find the corresponding replacement expression
@@ -1997,6 +2068,7 @@ ipa_param_body_adjustments::modify_call_stmt (gcall **stmt_p,
   gcall *stmt = *stmt_p;
   unsigned nargs = gimple_call_num_args (stmt);
   bool recreate = false;
+  gcc_assert (m_sorted_replacements_p);
 
   for (unsigned i = 0; i < gimple_call_num_args (stmt); i++)
     {
@@ -2029,19 +2101,11 @@ ipa_param_body_adjustments::modify_call_stmt (gcall **stmt_p,
       if (TREE_CODE (base) != PARM_DECL)
 	continue;
 
-      bool base_among_replacements = false;
-      unsigned j, repl_list_len = m_replacements.length ();
-      for (j = 0; j < repl_list_len; j++)
-	{
-	  ipa_param_body_replacement *pbr = &m_replacements[j];
-	  if (pbr->base == base)
-	    {
-	      base_among_replacements = true;
-	      break;
-	    }
-	}
-      if (!base_among_replacements)
+      ipa_param_body_replacement *first_rep
+	= lookup_first_base_replacement (base);
+      if (!first_rep)
 	continue;
+      unsigned first_rep_index = first_rep - m_replacements.begin ();
 
       /* We still have to distinguish between an end-use that we have to
 	 transform now and a pass-through, which happens in the following
@@ -2060,7 +2124,7 @@ ipa_param_body_adjustments::modify_call_stmt (gcall **stmt_p,
 	  recreate = true;
 	  gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
 	  pass_through_args.safe_push (i);
-	  pass_through_pbr_indices.safe_push (j);
+	  pass_through_pbr_indices.safe_push (first_rep_index);
 	  pass_through_offsets.safe_push (agg_arg_offset);
 	}
       else if (!by_ref && AGGREGATE_TYPE_P (TREE_TYPE (t)))
@@ -2078,7 +2142,7 @@ ipa_param_body_adjustments::modify_call_stmt (gcall **stmt_p,
 	    {
 	      recreate = true;
 	      pass_through_args.safe_push (i);
-	      pass_through_pbr_indices.safe_push (j);
+	      pass_through_pbr_indices.safe_push (first_rep_index);
 	      pass_through_offsets.safe_push (agg_arg_offset);
 	    }
 	}
diff --git a/gcc/ipa-param-manipulation.h b/gcc/ipa-param-manipulation.h
index 0281ac4d901..9cc957ae7bb 100644
--- a/gcc/ipa-param-manipulation.h
+++ b/gcc/ipa-param-manipulation.h
@@ -318,6 +318,10 @@ public:
   void register_replacement (tree base, unsigned unit_offset, tree replacement);
   /* Register a replacement decl for the transformation done in APM.  */
   void register_replacement (ipa_adjusted_param *apm, tree replacement);
+  /* Sort m_replacements and set m_sorted_replacements_p to true.  Users that
+     call register_replacement themselves must call the method before any
+     lookup and thus also any statement or expression modification.  */
+  void sort_replacements ();
   /* Lookup a replacement for a given offset within a given parameter.  */
   tree lookup_replacement (tree base, unsigned unit_offset);
   /* Lookup a replacement for an expression, if there is one.  */
@@ -367,6 +371,7 @@ private:
   unsigned get_base_index (ipa_adjusted_param *apm);
   ipa_param_body_replacement *lookup_replacement_1 (tree base,
 						    unsigned unit_offset);
+  ipa_param_body_replacement *lookup_first_base_replacement (tree base);
   tree replace_removed_params_ssa_names (tree old_name, gimple *stmt);
   bool modify_expression (tree *expr_p, bool convert);
   bool modify_assignment (gimple *stmt, gimple_seq *extra_stmts);
@@ -425,6 +430,10 @@ private:
      its this pointer and must be converted to a normal function.  */
 
   bool m_method2func;
+
+  /* True if m_replacements have ben sorted since the last insertion.  */
+
+  bool m_sorted_replacements_p;
 };
 
 void push_function_arg_decls (vec<tree> *args, tree fndecl);
diff --git a/gcc/omp-simd-clone.cc b/gcc/omp-simd-clone.cc
index 92b629b1021..0949b8ba288 100644
--- a/gcc/omp-simd-clone.cc
+++ b/gcc/omp-simd-clone.cc
@@ -1229,6 +1229,7 @@ ipa_simd_modify_function_body (struct cgraph_node *node,
 	j += vector_unroll_factor (node->simdclone->simdlen,
 				   simd_clone_subparts (vectype)) - 1;
     }
+  adjustments->sort_replacements ();
 
   tree name;
   FOR_EACH_SSA_NAME (i, name, cfun)
diff --git a/gcc/testsuite/g++.dg/ipa/pr108110.C b/gcc/testsuite/g++.dg/ipa/pr108110.C
new file mode 100644
index 00000000000..e9f3b5efc04
--- /dev/null
+++ b/gcc/testsuite/g++.dg/ipa/pr108110.C
@@ -0,0 +1,32 @@
+/* { dg-do compile } */
+/* { dg-options "-O3" } */
+
+void __throw_out_of_range_fmt(...);
+char *_M_p;
+struct Trans_NS___cxx11_basic_string {
+  long _M_string_length;
+  long _M_check___pos;
+  Trans_NS___cxx11_basic_string() {
+    long __length = 0;
+    _M_string_length = __length;
+  }
+  long size() { return _M_string_length; }
+  long foo___pos;
+  char foo() { return _M_p[foo___pos]; }
+  int compare() { __throw_out_of_range_fmt(_M_check___pos, _M_string_length); __builtin_trap(); }
+};
+bool str_starts_with(Trans_NS___cxx11_basic_string &str,
+                     Trans_NS___cxx11_basic_string prefix) {
+  if (str.size() < prefix.size())
+    str.compare();
+  for (; prefix.size();) {
+    char __trans_tmp_2 = prefix.foo();
+    if (__trans_tmp_2)
+      return false;
+  }
+  __builtin_trap();
+}
+void testStartsWith() {
+  Trans_NS___cxx11_basic_string s1, s2;
+  str_starts_with(s1, s2);
+}
