For each ByteRange instruction in [begin, end), computes a hint to execution engines: the delta to the next instruction (in flat) worth exploring iff the current instruction matched. Implements a coloring algorithm related to ByteMapBuilder, but in this case, colors are instructions and recoloring ranges precisely identifies conflicts between instructions. Iterating backwards over [begin, end) is
| 840 | // between instructions. Iterating backwards over [begin, end) is guaranteed to |
| 841 | // identify the nearest conflict (if any) with only linear complexity. |
| 842 | void Prog::ComputeHints(std::vector<Inst>* flat, int begin, int end) { |
| 843 | Bitmap256 splits; |
| 844 | int colors[256]; |
| 845 | |
| 846 | bool dirty = false; |
| 847 | for (int id = end; id >= begin; --id) { |
| 848 | if (id == end || |
| 849 | (*flat)[id].opcode() != kInstByteRange) { |
| 850 | if (dirty) { |
| 851 | dirty = false; |
| 852 | splits.Clear(); |
| 853 | } |
| 854 | splits.Set(255); |
| 855 | colors[255] = id; |
| 856 | // At this point, the [0-255] range is colored with id. |
| 857 | // Thus, hints cannot point beyond id; and if id == end, |
| 858 | // hints that would have pointed to id will be 0 instead. |
| 859 | continue; |
| 860 | } |
| 861 | dirty = true; |
| 862 | |
| 863 | // We recolor the [lo-hi] range with id. Note that first ratchets backwards |
| 864 | // from end to the nearest conflict (if any) during recoloring. |
| 865 | int first = end; |
| 866 | auto Recolor = [&](int lo, int hi) { |
| 867 | // Like ByteMapBuilder, we split at lo-1 and at hi. |
| 868 | --lo; |
| 869 | |
| 870 | if (0 <= lo && !splits.Test(lo)) { |
| 871 | splits.Set(lo); |
| 872 | int next = splits.FindNextSetBit(lo+1); |
| 873 | colors[lo] = colors[next]; |
| 874 | } |
| 875 | if (!splits.Test(hi)) { |
| 876 | splits.Set(hi); |
| 877 | int next = splits.FindNextSetBit(hi+1); |
| 878 | colors[hi] = colors[next]; |
| 879 | } |
| 880 | |
| 881 | int c = lo+1; |
| 882 | while (c < 256) { |
| 883 | int next = splits.FindNextSetBit(c); |
| 884 | // Ratchet backwards... |
| 885 | first = std::min(first, colors[next]); |
| 886 | // Recolor with id - because it's the new nearest conflict! |
| 887 | colors[next] = id; |
| 888 | if (next == hi) |
| 889 | break; |
| 890 | c = next+1; |
| 891 | } |
| 892 | }; |
| 893 | |
| 894 | Inst* ip = &(*flat)[id]; |
| 895 | int lo = ip->lo(); |
| 896 | int hi = ip->hi(); |
| 897 | Recolor(lo, hi); |
| 898 | if (ip->foldcase() && lo <= 'z' && hi >= 'a') { |
| 899 | int foldlo = lo; |