Flags/ConditionCode Model is broken

Hi all,

I've spent the day trying to understand setcc/select_cc intricacies,
and I thought I should mention that so far as I can tell, the modeling
of CPU flags, condition codes and therefore conditional instructions
seems pretty broken.

On the one hand there are the SDNPInFlag/SDNPOutFlag node properties
which allow you to mark an instruction as using or def-ing the CPU
flags (respectively). This seems like an effective model, as CPU-flag
modification can be seen as a kind of side-effect in many cases.

Something which is missing here is that it's not possible (SFAIK) to
change/add node properties on existing 'standard' nodes. So for
targets whose 'add' instruction modifies the flags, a custom ADD node
must be used. One can't use the 'instrinsic' add def-ed in
TargetSelectionDAG.td. Ideally it should be possible to use these
existing records, marking them as using or def-ing the flags.

In addition, setcc doesn't gel with this model at all. setcc expects
an explicit output operand. In order to properly fit in with the
'out-of-band' flags model, setcc should NOT have an explicit output,
but should always be SDNPOutFlag, and set the flags as its result.
Currently setcc is NOT SDNPOutFlag - this is just confusing and
broken.

In general, it would be really great if there was a 'unified flag
theory' :wink: If flags are modeled as CPU 'effects', then they should
ALWAYS be modeled as such. ALU and setcc operations should
(optionally) carry the SDNPOutFlag property. Any 'predicated' or
conditional instruction should be 'trivial' to implement, simply by
marking the instruction as SDNPInFlag, and specifying a conditioncode
parameter. This may require the addition of some kind of
condition-code base type to mark conditioncode operands.

Alternatively, CPU flags can be modeled using a special flags register
(or register class?). In which case, SNDPInFlag/SNDPOutFlag should be
killed, and all instructions which modify the flags (even as a
side-effect) should do so explicitly. In this case, setcc should
always set a special flags register.

Just my 2c.
Thoughts?

Hello,

I think you're misunderstanding ISD::SETCC. It really is
supposed to output a normal integer value, not a flags result.
It may help to think of SETCC as being similar to BR_CC and
SELECT_CC. In each of these operators, an implicit flags
value is implicitly produced and consumed, and not exposed
for use by other operators. The difference between the three
is what the consumer does. In SETCC, the consumer reads
the flags value and produces an integer value. This is
needed to implement C code like "int x = y < z;", for example.

As for Flags, CodeGen is gradually moving to using explicit
registers to replace Flags in many cases. This is an ongoing
project, driven by people contributing things as they need
them. You are welcome to contribute.

That ISD::ADD and other "standard" nodes cannot be extended
in target-specific ways is not accidental; these exist to support
target-independent lowering and optimization.

Dan

Hi all,

I've spent the day trying to understand setcc/select_cc intricacies,
and I thought I should mention that so far as I can tell, the modeling
of CPU flags, condition codes and therefore conditional instructions
seems pretty broken.

On the one hand there are the SDNPInFlag/SDNPOutFlag node properties
which allow you to mark an instruction as using or def-ing the CPU
flags (respectively). This seems like an effective model, as CPU-flag
modification can be seen as a kind of side-effect in many cases.

That's not it at all. These model instructions reading / writing MVT::Flag a value. That just mean from the scheduler's point of view the node that produces a MVT::Flag and the user have to be scheduled together.

Evan

That’s not it at all. These model instructions reading / writing

MVT::Flag a value. That just mean from the scheduler’s point of view

the node that produces a MVT::Flag and the user have to be scheduled

together.

Wow. That’s just super confusing.

So SDNPInFlag/SNDPOutFlag is used only for scheduling?

I think you’re misunderstanding ISD::SETCC.

I may well be misunderstanding setcc, but my misunderstanding is due, at least in part, to the lack of clarity in the model. Also, why are conditional branches modeled in the Initial Selection DAG as a setcc/brcond pair? This seems a little off.

That ISD::ADD and other “standard” nodes cannot be extended

in target-specific ways is not accidental; these exist to support

target-independent lowering and optimization.

Understood. Surely there should be some way to ‘tack on’ the flags related properties target-independent lowering and target-dependent lowering. It should not be necessary for a target-implementor to effectively reimplement al these ‘standard’ nodes in order to add something so ‘trivial’.

As for Flags, CodeGen is gradually moving to using explicit

registers to replace Flags in many cases. This is an ongoing

project, driven by people contributing things as they need

them. You are welcome to contribute.

This seems like a good plan. Anything which makes the model more coherent is a GoodThing. Where is this documented?

All in all, it would be great if there were a unified way of modeling conditional (flags-based) operations, that is useful both during instruction selection and scheduling. I’m more than happy to help in whatever way I can to push this amazing tool forward :wink:

Justin.

> That's not it at all. These model instructions reading / writing
> MVT::Flag a value. That just mean from the scheduler's point of view
> the node that produces a MVT::Flag and the user have to be scheduled
> together.

Wow. That's just super confusing.

So SDNPInFlag/SNDPOutFlag is used only for scheduling?

It's not really that confusing... in a sense, the flags don't
represent any register at all, but if you consider the flag operand to
represent all of the fixed physical registers defined by an
instruction, it should be less confusing. The scheduler
conservatively assumes that any instruction could clobber the physical
registers the flag operand represents, so it puts the instructions
next to each other.

I think you're misunderstanding ISD::SETCC.

I may well be misunderstanding setcc, but my misunderstanding is due, at
least in part, to the lack of clarity in the model. Also, why are
conditional branches modeled in the Initial Selection DAG as a setcc/brcond
pair? This seems a little off.

It's because that's the simplest way to transform LLVM IR; branch
instructions take an arbitrary i1, which might not be the output of a
conditional (one common case is that it could be a logical or of two
conditionals). brcond is roughly equivalent to the LLVM IR br
instruction, and setcc is roughly equivalent to the LLVM IR icmp
instruction. The DAGCombiner changes the setcc/brcond combination
into a brcc if it's possible and the target wants it. Note that for
architectures without an arithmetic flag register, like Alpha, the
standard conditional branch sequence looks a lot like a setcc+brcond.

That ISD::ADD and other "standard" nodes cannot be extended

in target-specific ways is not accidental; these exist to support

target-independent lowering and optimization.

Understood. Surely there should be some way to 'tack on' the flags related
properties target-independent lowering and target-dependent lowering. It
should not be necessary for a target-implementor to effectively reimplement
al these 'standard' nodes in order to add something so 'trivial'.

It's been sort of considered, but the issue is that the cross-platform
code basically can't touch an addition that has an extra flag result
anyway... it would be a large amount of work to track down all the
places that make "bad" assumptions about standard operations, and it
wouldn't be a significant benefit anyway.

As for Flags, CodeGen is gradually moving to using explicit
registers to replace Flags in many cases. This is an ongoing
project, driven by people contributing things as they need
them. You are welcome to contribute.

This seems like a good plan. Anything which makes the model more coherent is
a GoodThing. Where is this documented?

Most of the work here is in the x86 backend, although there have been
fixes for some nasty bugs in cross-platform code...

-Eli