Brad Fitzpatrick (brad) wrote,
Brad Fitzpatrick

MIPS, I forgive you.

Now that I understand you, I no longer hate you.
Most everything's working now.
I added runtime array index bounds checking too.
3 extra instructions per array access. Bleh.

I'm convinced that a lot of bounds checking can be done at compile time... if you wanted to write a language that was safe, i'm sure you could get a compiler to remove a lot of the instructions to check array access and only leave in the ones where the index was unknown (like if it was coming from user input).

you'd just need to make a data structure to represent sets efficiently (easy) and then for each variable used, figure out what values it can take on at any point in the program. For a loop (the place you'd like to remove array bounds checking the most) the set's easy if the loop iterator is your array index... the set is usually [start, finish] (in a language with a for statment like for StartExpr to EndExpr). it gets more complicated if the language lets you do stuff like C and specify code to run on every loop iteration to keep going or not. hrm.. there's a trade-off between writing in a low level language like C that's fast but the compiler can't tell what you're doing and thus can't optimize much and writing in a higher level language that's slower (at least for the naive implementation) but where it really good optimizations could potentially be made since it's obvious what you're doing.

hm. i'm rambling. the above makes little sense.

back to homework.

  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment