while ( ($p = index $haystack, $needle, $p+1) > -1 ) {
    # e.g. (not tested)
    pos($haystack) = $p;
    $p = pos($haystack) if $str =~ s{ \G ... }{...}cxms
        # regex doing the tough dishes
    ;   # /c flag: preserve pos() on non-match
}