Index: include/algorithm
===================================================================
--- include/algorithm
+++ include/algorithm
@@ -841,7 +841,7 @@
 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
 {
     for (; __first != __last; ++__first)
-        if (!__pred(*__first))
+        if (!__pred(as_const(*__first)))
             return false;
     return true;
 }
@@ -855,7 +855,7 @@
 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
 {
     for (; __first != __last; ++__first)
-        if (__pred(*__first))
+        if (__pred(as_const(*__first)))
             return true;
     return false;
 }
@@ -929,7 +929,7 @@
 find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
 {
     for (; __first != __last; ++__first)
-        if (__pred(*__first))
+        if (__pred(as_const(*__first)))
             break;
     return __first;
 }
@@ -1147,7 +1147,7 @@
         _ForwardIterator __i = __first;
         while (++__i != __last)
         {
-            if (__pred(*__first, *__i))
+            if (__pred(as_const(*__first), as_const(*__i)))
                 return __first;
             __first = __i;
         }
Index: test/std/algorithms/alg.nonmodifying/alg.adjacent.find/adjacent_find_pred.pass.cpp
===================================================================
--- test/std/algorithms/alg.nonmodifying/alg.adjacent.find/adjacent_find_pred.pass.cpp
+++ test/std/algorithms/alg.nonmodifying/alg.adjacent.find/adjacent_find_pred.pass.cpp
@@ -19,7 +19,7 @@
 
 #include "test_macros.h"
 #include "test_iterators.h"
-
+#include "test_predicates.h"
 
 #if TEST_STD_VER > 17
 TEST_CONSTEXPR bool eq (int a, int b) { return a == b; }
@@ -51,6 +51,11 @@
                               std::equal_to<int>()) ==
                               forward_iterator<const int*>(ia+sa));
 
+    // Test that const overloads are used
+    std::adjacent_find(std::begin(ia),
+                       std::end(ia),
+                       force_const_predicate<int>());
+
 #if TEST_STD_VER > 17
     static_assert(test_constexpr());
 #endif
Index: test/std/algorithms/alg.nonmodifying/alg.all_of/all_of.pass.cpp
===================================================================
--- test/std/algorithms/alg.nonmodifying/alg.all_of/all_of.pass.cpp
+++ test/std/algorithms/alg.nonmodifying/alg.all_of/all_of.pass.cpp
@@ -17,6 +17,7 @@
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "test_predicates.h"
 
 struct test1
 {
@@ -45,6 +46,11 @@
                            input_iterator<const int*>(ia + sa), test1()) == true);
         assert(std::all_of(input_iterator<const int*>(ia),
                            input_iterator<const int*>(ia), test1()) == true);
+
+        // Test that const overloads are used
+        std::all_of(std::begin(ia),
+                    std::end(ia),
+                    force_const_predicate<int>());
     }
     {
         const int ia[] = {2, 4, 5, 8};
Index: test/std/algorithms/alg.nonmodifying/alg.any_of/any_of.pass.cpp
===================================================================
--- test/std/algorithms/alg.nonmodifying/alg.any_of/any_of.pass.cpp
+++ test/std/algorithms/alg.nonmodifying/alg.any_of/any_of.pass.cpp
@@ -17,6 +17,7 @@
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "test_predicates.h"
 
 struct test1
 {
@@ -45,6 +46,10 @@
                            input_iterator<const int*>(ia + sa), test1()) == true);
         assert(std::any_of(input_iterator<const int*>(ia),
                            input_iterator<const int*>(ia), test1()) == false);
+        // Test that const overloads are used
+        std::any_of(std::begin(ia),
+                    std::end(ia),
+                    force_const_predicate<int>());
     }
     {
         const int ia[] = {2, 4, 5, 8};
Index: test/std/algorithms/alg.nonmodifying/alg.find/find_if.pass.cpp
===================================================================
--- test/std/algorithms/alg.nonmodifying/alg.find/find_if.pass.cpp
+++ test/std/algorithms/alg.nonmodifying/alg.find/find_if.pass.cpp
@@ -19,6 +19,7 @@
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "test_predicates.h"
 
 struct eq {
     TEST_CONSTEXPR eq (int val) : v(val) {}
@@ -50,6 +51,11 @@
                      eq(10));
     assert(r == input_iterator<const int*>(ia+s));
 
+    // Test that const overloads are used
+    std::find_if(std::begin(ia),
+                 std::end(ia),
+                 force_const_predicate<int>());
+
 #if TEST_STD_VER > 17
     static_assert(test_constexpr());
 #endif
Index: test/support/test_predicates.h
===================================================================
--- /dev/null
+++ test/support/test_predicates.h
@@ -0,0 +1,29 @@
+struct stateful_predicate
+{
+    stateful_predicate (int i) : i_(i) {};
+    ~stateful_predicate() { i_ = -32767; }
+    bool operator() (const stateful_predicate &p) const { return p.i_ == i_; }
+
+    bool operator==(int i) const { return i == i_;}
+    int i_;
+};
+
+template <typename T>
+struct force_const_predicate
+{
+    T value;
+    force_const_predicate(T value = 1) : value(value) {}
+
+    bool operator()(T&) { assert(false); return false; }
+    bool operator()(const T&p) const { return value == p; }
+    bool operator()(T&, T&) { assert(false); return false; }
+    bool operator()(const T&p0, const T&p1) const { return p0 == p1; }
+    bool operator==(T&) { assert(false); return false; }
+    bool operator==(const T&p) const { return value == p; }
+    bool operator!=(T&) { assert(false); return false; }
+    bool operator!=(const T&p) const { return value != p; }
+    bool operator< (T&) { assert(false); return false; }
+    bool operator< (const T&p) const { return value < p; }
+    bool operator> (T&) { assert(false); return false; }
+    bool operator> (const T&p) const { return value > p; }
+};
\ No newline at end of file