diff --git a/src/regexp.c b/src/regexp.c
index f19e139..6e5655a 100644
--- a/src/regexp.c
+++ b/src/regexp.c
@@ -8011,13 +8011,10 @@
     bt_regcomp,
     bt_regfree,
     bt_regexec_nl,
-    bt_regexec_multi
-#ifdef DEBUG
-    ,(char_u *)""
-#endif
+    bt_regexec_multi,
+    (char_u *)""
 };
 
-
 #include "regexp_nfa.c"
 
 static regengine_T nfa_regengine =
@@ -8025,18 +8022,14 @@
     nfa_regcomp,
     nfa_regfree,
     nfa_regexec_nl,
-    nfa_regexec_multi
-#ifdef DEBUG
-    ,(char_u *)""
-#endif
+    nfa_regexec_multi,
+    (char_u *)""
 };
 
 /* Which regexp engine to use? Needed for vim_regcomp().
  * Must match with 'regexpengine'. */
 static int regexp_engine = 0;
-#define	    AUTOMATIC_ENGINE	0
-#define	    BACKTRACKING_ENGINE	1
-#define	    NFA_ENGINE		2
+
 #ifdef DEBUG
 static char_u regname[][30] = {
 		    "AUTOMATIC Regexp Engine",
@@ -8083,10 +8076,8 @@
 	    regexp_engine = AUTOMATIC_ENGINE;
 	}
     }
-#ifdef DEBUG
     bt_regengine.expr = expr;
     nfa_regengine.expr = expr;
-#endif
 
     /*
      * First try the NFA engine, unless backtracking was requested.
@@ -8096,7 +8087,8 @@
     else
 	prog = bt_regengine.regcomp(expr, re_flags);
 
-    if (prog == NULL)	    /* error compiling regexp with initial engine */
+    /* Check for error compiling regexp with initial engine. */
+    if (prog == NULL)
     {
 #ifdef BT_REGEXP_DEBUG_LOG
 	if (regexp_engine != BACKTRACKING_ENGINE)   /* debugging log for NFA */
@@ -8114,13 +8106,27 @@
 	}
 #endif
 	/*
-	 * If the NFA engine failed, the backtracking engine won't work either.
+	 * If the NFA engine failed, try the backtracking engine.
+	 * Disabled for now, both engines fail on the same patterns.
+	 * Re-enable when regcomp() fails when the pattern would work better
+	 * with the other engine.
 	 *
 	if (regexp_engine == AUTOMATIC_ENGINE)
+	{
 	    prog = bt_regengine.regcomp(expr, re_flags);
+	    regexp_engine == BACKTRACKING_ENGINE;
+	}
 	 */
     }
 
+    if (prog != NULL)
+    {
+	/* Store the info needed to call regcomp() again when the engine turns
+	 * out to be very slow when executing it. */
+	prog->re_engine = regexp_engine;
+	prog->re_flags  = re_flags;
+    }
+
     return prog;
 }
 
@@ -8135,20 +8141,75 @@
 	prog->engine->regfree(prog);
 }
 
+#ifdef FEAT_EVAL
+static void report_re_switch __ARGS((char_u *pat));
+
+    static void
+report_re_switch(pat)
+    char_u *pat;
+{
+    if (p_verbose > 0)
+    {
+	verbose_enter();
+	MSG_PUTS(_("Switching to backtracking RE engine for pattern: "));
+	MSG_PUTS(pat);
+	verbose_leave();
+    }
+}
+#endif
+
+static int vim_regexec_both __ARGS((regmatch_T *rmp, char_u *line, colnr_T col, int nl));
+
 /*
  * Match a regexp against a string.
  * "rmp->regprog" is a compiled regexp as returned by vim_regcomp().
  * Uses curbuf for line count and 'iskeyword'.
+ * When "nl" is TRUE consider a "\n" in "line" to be a line break.
  *
  * Return TRUE if there is a match, FALSE if not.
  */
+    static int
+vim_regexec_both(rmp, line, col, nl)
+    regmatch_T	*rmp;
+    char_u	*line;  /* string to match against */
+    colnr_T	col;    /* column to start looking for match */
+    int		nl;
+{
+    int result = rmp->regprog->engine->regexec_nl(rmp, line, col, nl);
+
+    /* NFA engine aborted because it's very slow. */
+    if (rmp->regprog->re_engine == AUTOMATIC_ENGINE
+					       && result == NFA_TOO_EXPENSIVE)
+    {
+	int    save_p_re = p_re;
+	int    re_flags = rmp->regprog->re_flags;
+	char_u *pat = vim_strsave(((nfa_regprog_T *)rmp->regprog)->pattern);
+
+	p_re = BACKTRACKING_ENGINE;
+	vim_regfree(rmp->regprog);
+	if (pat != NULL)
+	{
+#ifdef FEAT_EVAL
+	    report_re_switch(pat);
+#endif
+	    rmp->regprog = vim_regcomp(pat, re_flags);
+	    if (rmp->regprog != NULL)
+		result = rmp->regprog->engine->regexec_nl(rmp, line, col, nl);
+	    vim_free(pat);
+	}
+
+	p_re = save_p_re;
+    }
+    return result;
+}
+
     int
 vim_regexec(rmp, line, col)
-    regmatch_T *rmp;
-    char_u      *line;  /* string to match against */
-    colnr_T     col;    /* column to start looking for match */
+    regmatch_T	*rmp;
+    char_u	*line;
+    colnr_T	col;
 {
-    return rmp->regprog->engine->regexec_nl(rmp, line, col, FALSE);
+    return vim_regexec_both(rmp, line, col, FALSE);
 }
 
 #if defined(FEAT_MODIFY_FNAME) || defined(FEAT_EVAL) \
@@ -8158,11 +8219,11 @@
  */
     int
 vim_regexec_nl(rmp, line, col)
-    regmatch_T *rmp;
-    char_u *line;
-    colnr_T col;
+    regmatch_T	*rmp;
+    char_u	*line;
+    colnr_T	col;
 {
-    return rmp->regprog->engine->regexec_nl(rmp, line, col, TRUE);
+    return vim_regexec_both(rmp, line, col, TRUE);
 }
 #endif
 
@@ -8183,5 +8244,32 @@
     colnr_T     col;            /* column to start looking for match */
     proftime_T	*tm;		/* timeout limit or NULL */
 {
-    return rmp->regprog->engine->regexec_multi(rmp, win, buf, lnum, col, tm);
+    int result = rmp->regprog->engine->regexec_multi(
+						rmp, win, buf, lnum, col, tm);
+
+    /* NFA engine aborted because it's very slow. */
+    if (rmp->regprog->re_engine == AUTOMATIC_ENGINE
+					       && result == NFA_TOO_EXPENSIVE)
+    {
+	int    save_p_re = p_re;
+	int    re_flags = rmp->regprog->re_flags;
+	char_u *pat = vim_strsave(((nfa_regprog_T *)rmp->regprog)->pattern);
+
+	p_re = BACKTRACKING_ENGINE;
+	vim_regfree(rmp->regprog);
+	if (pat != NULL)
+	{
+#ifdef FEAT_EVAL
+	    report_re_switch(pat);
+#endif
+	    rmp->regprog = vim_regcomp(pat, re_flags);
+	    if (rmp->regprog != NULL)
+		result = rmp->regprog->engine->regexec_multi(
+						rmp, win, buf, lnum, col, tm);
+	    vim_free(pat);
+	}
+	p_re = save_p_re;
+    }
+
+    return result;
 }