Saturday, September 6, 2014

It wasn't any fun, but I finally got division working. Sample output at the end of this. The main problem is that proper signed division uses a lot of code. My intent was to provide the optimizer with enough information to pare this down to the minimum number of required operations.

There were a few problems though. I was trying to implement signed division using register constraints and lots of scratch registers for the temporaries, but that whole approach does not work.

At the time when the compiler is deciding which patterns to use for the initial RTL representation, it does not look at operand constraints. This means that having special behavior for constants or restricting division to valid data locations will not work. The compiler just takes whatever RTL is defined for an operation and adds it to the instruction stream. If that happens to be incorrect, the user will get compiler crashes or badly broken code.

One test I ran was just a short loop with a dividends between -10 and 10. The broken division code turned this into an infinite loop with an oscillating dividend. Not even close to working code.

Eventually I got this to work by using instruction expanders. This lets the compiler figure out which branches are needed for a given input and uses registers optimally. This needed five more temporary registers and expanding the single division instruction to eleven different ones, including a wrapper around unsigned division which itself is not much fun. A lot of these steps get optimized away if not needed.

Fortunately, no one needs to care about this but me.

Have some sample code:

eric@compaq:~/dev/tios/src/temp$ cat div_signed.c
      int div(int a, int b) {return a/b;}
eric@compaq:~/dev/tios/src/temp$ cat div_signed.s
      def div
      mov r1, r5
      xor r2, r5
      abs r2
      clr r3
      mov r1, r4
      abs r4
      div r2, r3
      mov r3, r1
      inv r5
      jlt $+4
      neg r1
      b *r11

Next up, improved adherence to Editor/Assembler syntax and conventions.

No comments:

Post a Comment