switches

Do you think you could provide an example? How would this code be compiled?

int bar(int x) {
    switch(x) {
       case 0:
         return 1;
       case 2:
       case 3:
         return foo(x);
       case 5:
         return 5;
       case 6:
         return 6;
       case 7:
         return 7;
       case 100:
         break;
       default:
         return 4;
    }
    return 3;
}

• This reply was modified 7 years, 6 months ago by  goldbug.

I had a play around with optimizing this with what I, probably incorrectly, think I understand about the hardware. Is the following a valid program for Silver?

F('bar') %0;
    con    (w(100ul))              %1,  //          F3 ↥
    rd     (w(1ul))                %2,  // R0          ↥
    rd     (w(3ul))                %3,  // R0          ↥
    rd     (w(4ul))                %4,  // R1          ↥
    eql    (b4 %0,  b3 %1)         %5,  //    E0       ▸
    gtrs   (b4 %0,      7)         %6,  //    E1       ▸
    gtrs   (b4 %0,      3)         %7,  //    E2       ▸
    eql    (b4 %0,      0)         %8,  //    E3       ▸
    pick   (b0 %8,  b6 %2, b6 %4)  %9,  //       P0    ?
    retntr (b4 %5,  b6 %3),             //          F0 ↦
    retntr (b3 %6,  b5 %4),             //          F1 ↦
    retntr (b2 %7,  b9 %0);             //          F2 ↦

    gtrs   (b9 %0,      1)         %10, //    E0       ▸
    calltr1(b0 %10, 'foo', b10 %0) %11, //          F0 ↱
    retnfl (b1 %10, b2 %9),             //          F1 ↦
    retn   (b1 %11);                    //          F2 ↦

Is there a reference for conAsm? I can’t figure out what half the operations do.

I am very impressed that the compiler & specializer managed to condense my test case to just 4 instructions! WOW.

I finally managed to digest that code, impressive indeed!

I can also see that it would be easy to make the entire function just 1 instruction in gold.

Veedrac also has the right idea about how to format conAsm. He puts the rd and con operations first which more closely resembles phasing, he spaces instructions so that it is easy to visually scan the code and he shows in comments the slot where the result go. I am not sure what the arrows at the end mean though.

I also tried my hand at this guy for Gold, and got

// ILP of 5⅓, mostly because of the silly load latency :P.
F("parseval") %str;
    load(%str, 0, b) %l0,
    load(%str, 1, b) %l1, // I'd fill this with loads if the two loops had the
    load(%str, 2, b) %l2; // same cycle length, but alas they do not.

    eqlb(%l0, 45) %neg,
    addp(%str, 1, b) %strplus1,
    pick(%neg, %strplus1, %str) %start,
    pick(%neg, %l1, %l0) %L0,
    pick(%neg, %l2, %l1) %L1;

    // Now we can finally start doing fun stuff.
    rd(b(0)) %zero,
    load(%start, 2, b) %char,     // Not loading early means we take a stall in hexmode,
    eqlb(%L0,   48) %L00,         // but loading early means decimalmode gets early loads. :(
    eqlb(%L1,  120) %L1x,
    addp(%start, 2) %startplus2,
    pick(%L00, %L1x, %L00) %hexmode,
    innertr(%hexmode, "parseval$hexmode", %zero, %startplus2, %neg),
    inner(%decimalmode, "parseval$decimalmode", %zero, %startplus2, %L1, %L0, %neg);

// ILP of 9! Cycle length equals loop-caried dependency.
L("parseval$hexmode") %total %str %neg;
    // a wild %char appears, right on time!
    load  (%str, b, 2) %char,     // Ideally this load would be fetching further ahead,
    gequ  (%char,  48) %digitlo,  // but we want one byte every 2 cycles, whereas the
    lequ  (%char,  57) %digithi,  // other branch want one every 3 cycles, so you can't
    gequ  (%char,  97) %letterlo, // hoist the setup into the header.
    lequ  (%char, 102) %letterhi,
    sub   (%char,  48) %digitval,
    sub   (%char,  87) %letterval,
    shiftl(%total,  4) %shifttot,
    addp  (%str, 1, b) %newstr,
    pick  (%digitlo,  %digithi,  %digitlo)  %digit,
    pick  (%letterlo, %letterhi, %letterlo) %letter;

    orl   (%digit,    %letter)    %inrange,
    add   (%shifttot, %digitval)  %digittot,
    add   (%shifttot, %letterval) %lettertot,
    pick  (%digit, %digittot, %lettertot) %newtotal,
    conform(%newtotal, %newstr, %neg, %total, %char),
    leavefl(%inrange, "parseval$finish", %total, %char, %neg),
    br("parseval$hexmode");

// ILP of only 4⅓. Cycle length equals loop-caried dependency.
// Not much one can do when the multiply is slow... :(
L("parseval$decimalmode") %total %str %newchar %char %neg;
    // A wild %newnewchar appears... six cycles early.
    // That's pretty lame, but fixing it take a branch.
    load  (%str, b, 3) %newnewchar,
    gequ  (%char,  48) %digitlo,
    lequ  (%char,  57) %digithi,
    addp  (%str, 1, b) %newstr,
    sub   (%char,  48) %digitval,
    shiftl(%total,  1) %totalx2,
    shiftl(%total,  3) %totalx8,
    pick  (%digitlo, %digithi,  %digitlo) %digit,
    leavefl(%digit, "parseval$finish", %total, %char, %neg);

    // This is a very sad instruction.
    add   (%totalx2,  %totalx8)  %totalx10;

    add   (%totalx10, %digitval) %newtotal,
    rescue(%newtotal, %newstr, %newnewchar, %newchar, %neg),
    br("parseval$hexmode");

// ILP of 4½. Meh, it works.
L("parseval$finish") %total %char %neg;
    // a wild %fakechar appears
    eqlb(%char, 75) %K,
    eqlb(%char, 77) %M,
    neg(%total) %negtotal,
    pick(%neg, %negtotal, %total) %totalsigned;

    shiftl(%totalsigned, 10) %totalK,
    shiftl(%totalsigned, 20) %totalM,
    pick(%K, %totalK, %totalsigned) %totalelse,
    retntr(%M, %totalM),
    retn(%totalelse);

Interesting architecture indeed. I’ve not handled the busywork belt numbers, but I’ve checked they’re in a consistent position. I expect one’s better off having a branch before entering either loop where you flood it with correctly-delayed loads ahead of time; that way you don’t risk stalls in the loop itself, but it adds a cycle (and a jump) to every call to parseval. Delayed loads don’t work because the loop count is different, and tagged loads don’t work because they don’t pipeline.

• This reply was modified 7 years, 6 months ago by  Veedrac.

1. Sure, you can use retire to get you that fetch-ahead load if you don’t mind stalling while the loop warms up. Alternatively you can just fix the instruction set so I can do it the right way ;).

2. Neat, I knew there must be something like that. It was too obvious to overlook.

6, 7, 8. I explicitly chose not to unroll or vectorize to make the comparison more meaningful. I’m sure these things work, but I tried to stick to things an OoO core would be trying to do in hardware. No maths tricks beyond what I could believe stock GCC would give.

• This reply was modified 7 years, 6 months ago by  Veedrac.

I’d love to explain the thing you’re missing and how to fix it, but alas I expect there exist lawyers that would be upset if I did. You’re going to have to take what you’ve got.

At the risk of diverging the topic, I’m wondering at the impact of different optimization settings on code size. With the architectures I’m familiar with, -O3 and above have an unfortunate tendency to produce larger code in the interest of speed. But techniques like unwinding loops don’t appear to be desirable on the Mill.

I’m very excited to see how to implement an interpreter minus megamorphic dispatch. Is the talk from Wednesday available somewhere?

So I come back to the site to check what’s new and I find a 1:20 hours lecture on how you compiled my code and even credited me for it.

Priceless!

Tx Ivan, you talks are really interesting and fun to watch.

The pick can be used to build a range check. For example, to check if (x >=4 && x <= 7) one could write:

F("bar") %0;
    rd     (w(0ul))               %1,
    geqs   (b1 %0, 4)             %2,
    leqs   (b2 %0, 7)             %3,
    pick   (b1 %2, b0 %3, b2 %1)  %4;

Range checks would be fairly common in switches. In this example, if (2 <= x <= 3) it should call foo(), and if (4 <= x <= 7) it can return x. It seems like a fairly simple optimization to add to the specializer instead of a bunch of eql. Range checks could also be useful to perform array bounds check.

The only issue is that, if I understand the phasing correctly, the result of the pick cannot be used in the calltr1 within the same instruction.

I must admit I scratched my head a bit about the fma operation. For the life of me I can’t imagine it being used that often. It seems like an oddly specific instruction to add, but maybe I am missing something. If you can have operations use more than one ALU, then perhaps a “between” operation would be useful that would do range check. As shown above it can easily be done with a pick, but there could be a gain if the result of the between operation was usable in calltr1.

• This reply was modified 7 years, 3 months ago by  goldbug.

The pick operation can be used to build a range check. For example, to check if (x >=4 && x <= 7) one could write:

F("bar") %0;
    rd     (w(0ul))               %1,
    geqs   (b1 %0, 4)             %2,
    leqs   (b2 %0, 7)             %3,
    pick   (b1 %2, b0 %3, b2 %1)  %4;

Range checks would be fairly common in switches. In this example, if (2 <= x && x <= 3) it should call foo(), and if (4 <= x && x <= 7) it can return x. It seems like a fairly simple optimization to add to the specializer instead of a bunch of eql. Range checks could also be useful to perform array bounds check.

The only issue, if I understand phasing correctly, is that the result of a pick cannot be used in a calltr1 within the same instruction.

I must admit I scratched my head a bit about the fma operation. For the life of me I can’t imagine it being used that often. It seems like an oddly specific instruction to add, but maybe I am missing something. If you can have operations that use more than one ALU, then perhaps a “between” operation that does a range check would be useful. As shown above it can easily be done with a pick, but there could be a gain if the result of the between operation was usable in calltr1.

• This reply was modified 7 years, 3 months ago by  goldbug.
• This reply was modified 7 years, 3 months ago by  goldbug.

Sorry if it looks like I am spamming, the forum keeps deleting my post.

The pick operation can be used to build a range check. For example, to check if (x >=4 && x <= 7) one could write:

F("bar") %0;
    rd     (w(0ul))               %1,
    geqs   (b1 %0, 4)             %2,
    leqs   (b2 %0, 7)             %3,
    pick   (b1 %2, b0 %3, b2 %1)  %4;

Range checks would be fairly common in switches. In this example, if (2 <= x && x <= 3) it should call foo(), and if (4 <= x && x <= 7) it can return x. It seems like a fairly simple optimization to add to the specializer instead of a bunch of eql. Range checks could also be useful to perform array bounds check.

The only issue, if I understand phasing correctly, is that the result of a pick cannot be used in a calltr1 within the same instruction.

I must admit I scratched my head about the fma operation. For the life of me I can’t imagine it being used that often. It seems like an oddly specific instruction to add, but maybe I am missing something. If you can have operations that use more than one ALU, then perhaps a “between” operation that does a range check would be useful. As shown above it can easily be done with a pick, but there could be a gain if the result of the between operation was usable in calltr1.

I thought of a better way. The mill supports vector reducing operations like all and any. I don’t know the syntax for them, but perhaps the between operation could take a number and a vector and tell you if the number is in that range. for example:

F("bar") %0;
    con     (v(4ul, 7ul))         %1,  // whatever syntax to build a vector
    betw    (b1 %0, b0 %1)        %2;  // true if 4 <= x && x <= 7

Since the value is a vector, it can use only one functional unit to calculate if x is within the range. That would make switches ranges trivial to optimize.