[legalize-types] Remove stale entries from SoftenedFloats.

[fhahn]

Summary

When replacing a SDValue, we should remove the replaced value from
SoftenedFloats (and possibly the other maps as well?).

When we revisit a Node because it needs analyzing again, we have to
remove all result values from SoftenedFloats (and possibly other maps?).

This fixes the fp128 test failures with expensive checks for X86.

I think we probably should also remove the values from the other maps
(PromotedIntegers and so on), let me know what you think.

[fhahn]

D29180 tries to fix the same issues, by updating DAGTypeLegalizer::PerformExpensiveChecks to accept values in ReplacedValues and SoftenedFloats. I still think it would be better to properly clean up the stale entries.

[sepavloff]

Just a discussion about approach, as we both worked on the same problem :)

It looks like all these arrays, PromotedIntegers, SoftededFloats etc are in fact parts of one array that contains mapping of nodes to their replacement, they differ only by operation that created the replacement. They are useful only for error checking, otherwise their separate existence is useless. If it is true, we could have only one array, ReplacedValues that contained all such replacements. For the sake of checking we could keep few bits along with the replacement (in the form of PointerIntPair for instance) and check them when the replacement node is extracted or updated. Such checks would be cheap, they do not require search in tables, and they could be enabled in regular debug builds.

I have feeling that implementation of the legalizer is overcomplicated, and if we get rid of separate arrays for replacement nodes, the legalizer will become more clear and, may be, faster.

What do you think about such solution?

[fhahn]

In principle it sounds like a good idea to refactor the code and it indeed seems like the checks could be simplified. The main problem I think is that most of the code in DAGTypeLegalizer has not been touched for a very long time so it may be quite hard to find a reviewer. I think it would be ideal to merge this fix first and merge a bigger refactor later.

[fhahn]

@hfinkel Thanks again for the review Hal. Any chance you could also have a look at D29265, which also deals with type legalization?

[hfinkel]

In D29265#663071, @fhahn wrote:

@hfinkel Thanks again for the review Hal. Any chance you could also have a look at D29265, which also deals with type legalization?

I don't quite understand what's going on here. Can we visit a node, decide it needs to be a softened float, and then visit it again and make a different decision? Can't we already have used the result from the map?

[fhahn]

In D29265#663124, @hfinkel wrote:

In D29265#663071, @fhahn wrote:

@hfinkel Thanks again for the review Hal. Any chance you could also have a look at D29265, which also deals with type legalization?

I don't quite understand what's going on here. Can we visit a node, decide it needs to be a softened float, and then visit it again and make a different decision? Can't we already have used the result from the map?

For the X86 fp128 tests, the following is going on as far as I understand:

There is a node t9: f128 = select t8, t2, t4. During legalization of this node the following happens

• the result is softened
• the operands are scanned
• One integer operand is promoted
• The node has to be re-analyzed again, which means it's marked as NewNode again
• On the next iteration of the main loop, PerformExpensiveChecks fails because the result of t9: f128 = select t8, t2, t4 has been added to SoftenedFloats, but the node isn't marked as Processed yet.

But after thinking about it a little more I feel like there should be a better solution than my patch.

[pirama]

+chh for comments on fp128 legalization. I think a common ReplacedValues map that also tracks the kind of legalization performed would be useful - at the very least to understand how the different legalization steps interact and let us code in sanity checks.

[chh]

Could we have more info in this change or D29180?
Which recent change broke which tests? Could it be reverted?
What were the before and after regression IL trees?
Do we need new unit test?

Last time I fixed a regression related to fp128 in D26942.
The regression was introduced by a cleanup with nice intention,
but we just do not have enough unit tests. We only found
the regression too late to revert, when we tried to compile
a large Android code base. Yes, fp128 could work for all other
targets except Android's x86-64. The SoftenFloat* functions got into
infinite loop. So I would be very careful now about removing nodes
from SoftenedFloats.

[sepavloff]

In D29265#663586, @chh wrote:

Could we have more info in this change or D29180?
Which recent change broke which tests? Could it be reverted?
What were the before and after regression IL trees?
Do we need new unit test?

There is no failing test or apparent problems in the legalizer. The intent is to run builds with expensive checks enabled on regular basis. To do this we need reach clean state, when all tests pass.

The real problem in this that expensive checks have been turned off for a long time and algorithm of checking is out of sync with current implementation of the legalizer. Both this change and D29180 try to fix the check algorithm so that it won't report problems were they absent.

Last time I fixed a regression related to fp128 in D26942.
The regression was introduced by a cleanup with nice intention,
but we just do not have enough unit tests. We only found
the regression too late to revert, when we tried to compile
a large Android code base. Yes, fp128 could work for all other
targets except Android's x86-64. The SoftenFloat* functions got into
infinite loop. So I would be very careful now about removing nodes
from SoftenedFloats.

Absolutely agree. I think we should change only the check algorithm because the legalizer itself works as needed, at least we don't see any evidence that something is wrong with it.

The particular problem solved by this patch is that the check algorithm does not allow a replacement node be in both SoftenedFloats and ReplacedValues. I think it is wrong requirement. Essentially all the maps SoftenedFloats, ReplacedValues and other are in fact the same thing, a map from a node to its replacement. Nodes from ReplacedValues are allowed to be overridden, why those from SoftenedFloats are not? Probably the legalizer could be implemented in such way that the aforementioned maps remain disjoint, but current implementation breaks this condition.

[chh]

Could you modify existing fp128 unit tests, especially those for Android target, to run with both current configuration and the "expensive checks". How do you enable the "expensive checks"?

I remember dealing with some differences between SoftenedFloats and ReplacedValues maps, when I twisted various configurations to get fp128 values not softened for some operators and saved in mmx registers. I am afraid that a lot of cases were not tested with the "expensive checks" enabled.

[RKSimon]

In D29265#675246, @chh wrote:

Could you modify existing fp128 unit tests, especially those for Android target, to run with both current configuration and the "expensive checks". How do you enable the "expensive checks"?

I remember dealing with some differences between SoftenedFloats and ReplacedValues maps, when I twisted various configurations to get fp128 values not softened for some operators and saved in mmx registers. I am afraid that a lot of cases were not tested with the "expensive checks" enabled.

To enable all expensive checks is through a build define: LLVM_ENABLE_EXPENSIVE_CHECKS, to perform it on tests you have to enable the specific check in question, in this case "-enable-legalize-types-checking"

Really we need build bot coverage that has LLVM_ENABLE_EXPENSIVE_CHECKS defined by default, but that can't happen until we have fixed all the current failures.

[chh]

In D29180, I saw that fp16.ll was changed to run with -enable-legalize-types-checking. Could you add extra test runs with the -enable-legalize-types-checking flag, into current fp128 tests and some other tests depending on SoftenedFloats? Then some of those runs will pass only if this change to LegalizeTypes.cpp is applied, right?

Although I am not sure about the impact of this change to all SoftenedFloats targets, at least I have not seen regression in my local simple Android x86-64 build test. I hope someone else more familiar with this module can review this change. Thanks.

[fhahn]

Thank you for all the comments and sorry for my late response, I was away for the last 4 weeks.

I've added -enable-legalize-types-checking to guard against the problem even when building without expensive checks. I've also done a quick git bisect and it seems like the failure was introduced in D11438, but after I think it looks more like the failure surfaced because the patch enabled softening for fp128 types.

lib/CodeGen/SelectionDAG/LegalizeTypes.cpp

for (i = 0; i != NumOperands; ++i) {
       break;
     }
 
     // The sub-method updated N in place.  Check to see if any operands are new,
     // and if so, mark them.  If the node needs revisiting, don't add all users
     // to the worklist etc.
     if (NeedsReanalyzing) {
       assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?");
+
+      // Remove any result values from SoftenedFloats as N will be revisited
+      // again.
+      for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i)
+        SoftenedFloats.erase(SDValue(N, i));
+
       N->setNodeId(NewNode);
       // Recompute the NodeId and correct processed operands, adding the node to
       // the worklist if ready.
       SDNode *M = AnalyzeNewNode(N);
       if (M == N)
         // The node didn't morph - nothing special to do, it will be revisited.
         continue;
 
while (!NodesToAnalyze.empty()) {
         }
         // The original node continues to exist in the DAG, marked NewNode.
       }
     }
     // When recursively update nodes with new nodes, it is possible to have
     // new uses of From due to CSE. If this happens, replace the new uses of
     // From with To.
   } while (!From.use_empty());
+
+  SoftenedFloats.erase(From);
 }
 
 void DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) {
   assert(Result.getValueType() ==
          TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) &&
          "Invalid type for promoted integer");
   AnalyzeNewValue(Result);