2011/11/10 Jeff Law <l...@redhat.com>: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > On 11/09/11 14:09, Kai Tietz wrote: >> >> Well, such a comparison-logic-folder helper - like affine-tree for >> add/subtract/scale) - is for sure something good for inner gimple >> passes building up new logic-truth expressions, but such a pass >> doesn't meet requirements need to fold for BC optimization AFAICS. > Perhaps. I think the thing to do would be to see what additional > needs we have and evaluate if they make sense in that kind of framework. > >> >> The difference is that for BC we don't want to fold at all. Also >> it isn't necessarily "simplified" statement we want. For example >> 'if ((a | b) == 0 & ...) ...'. If the costs of such pattern '(a | >> b) == 0' are too high, we want to representation it instead as 'if >> (a == 0) if (b == 0) ...'. > We don't have to fold. Think of this as an easy to use on-the-side > representation of some operation(s). Well, this is clear, but I see here not much re-use between BC-optimization and general truth-logic folding.
The requirement that we need to handle comparisons for conditional folding is mainly caused by the cond_expr itself. As here we have no ssa-comparison statement itself. We have here left and right operand plus a comparison-code. So this kind of statement requires that we handle it in tree. Additional it might be a floating-point comparison, where logical-invert can't be done on comparison's code itself. So we need here to introduce a dummy expression for such cases (eg making a AST tree out of it). One of the major difference I see between expanding for general optimization vs. BC-optimization is the cost-analysis itself and the decision, if we want to exloide a statment into its sub-parts, or not.. For non-conditions, we don't want to look into multiple used statements at all, but for BC we might want that, as long as statement wasn't used before (in statement and dominators) Also costs of a statements operand depends on its use. Means an operand with multiple-use, which was prior to this statement evaluated, can be considered as simple-statments with costs of 1, but a statement with multiple use, which wasn't already evaluated has the costs of its operations. > What I would roughly expect to see is the set of operations feeding > the comparison shoved into this structure. With the full set of ops > exposed into this structure we could look at the cost, > canonicalize/simplify if appropriate, then select the best codegen > strategy, modifying the on-the-side structure as needed. We then > reflect the final result back into the IL. Well, the set of operations would be pretty limited IMHO. It would be logical and/or/not. May logical-xor could be interesting in some cases, but not really sure if it is worth to handle it all, as a logical-xor is normally a simple equal-compare in a condition. Additionally we need function to read in a conditional-expression from SSA-gimple form and built by it this representation and doing the comparison-expansion (means eliminating logical-not expressions and exploding some folded-patterns to their pure-logical expanded form - like (A | B) ==/!= 0, (A & B) ==/!= ~0 for integral-typed A,B, .And for boolean-typed A,B we might have things like A < B -> !A && B, etc. >> We have an condition 'if ((A | B) == 0 && C == 0) ...' where the >> joining of A == 0 and C == 0 would be profitable by >> BC-optimization, but the join of A != 0 and B != 0 isn't. So we do >> - as my patch does - first an expand to element comparison-sequence >> view. >> >> So we get for it the transformed form 'if (A == 0 && B == 0 && C == >> 0)'. > Right, so one of the first steps would be to canonicalize the (A|B) == > 0 && C == 0 form into something like you've shown above within this > on-the-side structure. Sure. with considering the "simple" characteristic of a gimple-statement and evaluating elements costs. >> Now we can begin to search for valid patterns in the condition for >> joining by searching from left-to-right for a profitable pattern. >> So we end-up with final statement 'if ((A | C) == 0 && C)' > Which would be fairly straighforward using the on-the-side structure. > > I'm not sure what I'm missing since the description you've given fits > very nicely with the overall approach Richi is suggesting. The point is here more, that I don't see a share-ability of this abstraction for BC and general condition-build-up, as the attributes for them are quite different. For a simple comparison-chain collector we need indeed just an inverse, and a helper-mode to represent intial condition-expression's compare. For BC we would need to make out of such a general tree a specialized one with the additional attributes and expansion logic before we can work on it at all. As for BC we have always to operate on already created SSA-gimple form, we don't need any operations on such a tree. We just read it in to our representation with calculating attributes, and then generating out of it the new representation for BC. And therefore I am questioning the approach to abstract this for general use with BC. Not in the approach itself. Kai
