Flags in arithmetic/logical operations

[wks]

This issue will give the client access to the flags set by arithmetic or logical operations, such as overflow, carry, zero, negative, ... This issue should only affect the BinOp instructions (ADD, SUB, MUL, ...).

The design should consider:

• scalar integral types
• scalar floating point types
• vector types

[wks]

Status Quo

CPUs usually use bits in a status register (EFLAGS/RFLAGS/APSR/PSTATE/CR/XER/...) to indicate unusual conditions in arithmetic operations or various results of comparing operations.

On x86, these flags (in EFLAGS/RFLAGS) are:

• CF: Carry Flag – carry, borrow, unsigned overflow
• PF: Parity Flag – the last significant byte has an even number of 1s
• AF: Auxiliary Carry Flag – carry or borrow out of bit 3 of the result. Useful in binary-coded decimal (BCD).
• ZF: Zero Flag – result is zero
• SF: Sign Flag – the most significant bit is 1, result is negative
• OF: Overflow Flag – signed overflow

ARMv7 defined these flags (in APSR):

• N: Negative – MSB=1, result is negative
• Z: Zero – result is zero
• C: Carry – carry, unsigned overflow
• V: Overflow – signed overflow
• Q: Overflow or Saturation

AArch64 defines the N, Z, C and V flags (in PSTATE), but also defines Q in the AArch32 mode.

POWER8 defines the following flags:
in CR0:

• LT: Negative
• GT: Positive
• EQ: Zero
• SO: Summary Overflow
  in XER:
• SO: Summary Overflow – Set when an instruction sets the overflow bit, but is only cleared by mtspr or mcrsr
• OV: Overflow – signed overflow
• CA: Carry – unsigned overflow

Apparently the only flags that are supported across these platforms are N, Z, C, V.

Floating point operations raise flags, too, as defined by IEEE754. SIMD instructions usually have their own ways to indicate such exceptions.

Proposed Mu Instruction Set Change:

Binary instructions now take zero or more flags. Flags can be #NEGA, #ZERO, #SOVF, #UOVF. For example:

// The old way
%rv = ADD <@T> %a %b

// De-opt when overflow
(%rv %sovf) = ADD [#SOVF] <@T> %a %b
BRANCH2 %sovf %deoptimize(...) %continue(...)

// Multiple flags are supported
(%rv %isNega %isZero %sovf %uovf) = ADD [#NEGA #ZERO #SOVF #UOVF] <@T> %a %b
%v1 = SELECT %isNega %x %y
%v2 = SELECT %isZero %x %y
%v3 = SELECT %sovf %x %y
%v4 = SELECT %uovf %x %y

In addition to the main result, each flag gives the instruction one extra result. All extra results are int<1>.

These flags can only be used with scalar integral arguments.

TODO

• Define the exact conditions under which each flag is set, for all binary operations applicable.
• Provide appropriate support for SIMD instructions and floating-point types.

Alternatives

• Currently some flags can be simulated by using the EQ, SLT or ULT instruction on the result, but may not be as efficient as integrating the flags into the arithmetic operations themselves.
• Treating these flags as thread-local flags, which can be queried from (common) instructions. But on some architectures (ARMv7, AArch64, POWER, for example), instructions may or may not set the flag depending on some flags in the instruction itself.

[wks]

NEGA and ZERO

#NEGA and #ZERO could be tested by a separate SLT or EQ comparison against 0.

  %v = ADD <@i64> %a %b
  %isNega = SLT <@i64> %v @I64_ZERO
  BRANCH2 %isNega %bb1(%v) %bb2()

%bb1(%v):
  %w = SUB <@i64> %v @I64_1

The back-end code generator can still merge the two instructions by performing tree-matching against these two instructions and identifying that the left operand is an ADD and the right operand is a zero. But if both the return value and the flag are used, a bottom-up style tree matcher still cannot model them as a tree.

If we want the Mu IR to be minimal, we can remove these flags. But since these flags are provide by the machine, they still have a reason to exist.

Exceptional branching

Some architectures (such as MIPS) can raise exceptions when overflow occurs. We can model this by using another flag, such as #SOVF_EXC, to enable this behaviour. It can be implemented on other architectures by a conditional branch.