<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On 27 February 2014 08:23, Stepan Dyatkovskiy <span dir="ltr"><<a href="mailto:stpworld@narod.ru" target="_blank">stpworld@narod.ru</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Hi Nick,<br>
<br>
I tried to rework changes as you requested. One of patches (0004 with extra assertions) has been removed.<div class=""><br>
<br>
> + bool isEquivalentType(Type *Ty1, Type *Ty2) const {<br>
> + return cmpType(Ty1, Ty2) == 0;<br>
> + }<br>
><br>
> Why do we still need isEquivalentType? Can we nuke this?<br></div>
Yup. After applying all the patches isEquivalentType will be totally replaced with cmpType. All isEqXXXX and friends will be removed in 0011 (old 0012). No traces left.<br>
Old function wasn't removed in 0001 just for keeping patches without extra noise like:<br>
<br>
- something that uses isEquivalentType<br>
+ something that uses cmpType<br>
<br>
The point is, that "something" that uses isEquivalentType, will be also replaced with one of next patches in this series.<div class=""><br>
<br>
><br>
> +static int cmpNumbers(uint64_t L, uint64_t R) {<br>
> + if (L < R) return -1;<br>
> + if (L > R) return 1;<br>
> + return 0;<br>
> +}<br>
><br>
> At a high level, you don't actually need a <=> operator to use a sort. A<br>
> strict ordering ( < operator) is sufficient. (Note that for mergefunc, a<br>
> strict weak ordering is not sufficient, it must be a total ordering.)<br></div>
That could be done with int FunctionComparator::compare(). We can replace it with bool FunctionComparator::less(). Though for all other cmp methods need at least 2 bits of information as result:<br>
1. Whether things are equal.<br>
2. Whether left less than right.<br>
<br>
As for FunctionComparator::compare(), conversion into less() will increase time of sanity check (patch #0010).<br>
Sanity check is just a sweet bonus. It checks that ordering implemented properly (checks order relation properties).<br>
Turning compare() into less() mean, that we'll have to run comparison two times: L.less(R) and R.less(L). But may be sanity check is not a thing to be published at all.<div class=""><br>
<br>
><br>
> Consider hoisting this inside the FunctionComparator class? That class<br>
> should have a bunch of implementations of comparisons between various<br>
> different things, which can pass down to other methods in the same class.<br></div>
In new patch series attached to this post, I have moved all static methods into FunctionComparator.<div class=""><br>
<br>
> + // Replacement for type::canLosslesslyBitCastTo, that<br>
> + // establish order relation on this kind of properties.<br>
> + int checkForLosslessBitcast(const Type *L, const Type *R);<br>
><br>
> Type:: not type:: . Please make this comment more descriptive.<br></div>
Done.<br>
[new comment]<br>
Replacement for Type::canLosslesslyBitCastTo, that<div class=""><br>
establish order relation on this kind of properties<br></div>
Returns 0, if L and R types could be converted to each other without<br>
reinterpretation of bits.<br>
Otherwise method returns -1 or 1, defining total ordering between<br>
types in context of lossless bitcastability trait.<br>
E.g.: if L is less than R (result is -1), than every type that could be<br>
losslessly bitcasted to L is less than R.<br>
[/new comment]<div class=""><br>
<br>
><br>
> + /// Replacement for C1 == getBitCast(C2, C1Ty)<br>
> + /// Its more controllable, and supposed to be simpler and more<br>
> predictionable.<br>
> + /// As very important advantage: it allows to introduce order relation on<br>
> + /// constants set, and thus use it as trait in refinement routines.<br>
><br>
> "Its" --> "It's". "predictionable" --> "predictable". And how is it more<br>
> predictable? I think this comment would be better if it described the<br>
> function instead of making comparisons between it and other functions.<br>
> Something like, "Compare constants under a system where pointer to X and<br>
> pointer to Y are considered equal" or whatever is actually true here.<br></div>
Done.<br>
[new comment]<div class=""><br>
Replacement for C1 == getBitCast(C2, C1Ty)<br></div>
Parses constants contents, assuming that types are losslessly<br>
bitcasted between each other. So actually it ignores types and only<br>
compares bits from L and R.<br>
Returns 0, if L and R has equivalent content.<br>
-1 or 1 if values are different. Maintaining total ordering requires<br>
two values that indicates non-equivalence (L less R, L greater R).<br>
[/new comment]<div class=""><br>
<br>
><br>
> +enum ConstantType {<br>
> I'm not sure that this buys you much. All the "isa" tests can be broken<br>
> down into a switch on getValueID() with the one exception of isNullValue().<br></div>
Done.<div class=""><br>
<br>
> + assert(<br>
> + C1->getType()-><u></u>canLosslesslyBitCastTo(C2-><u></u>getType()) &&<br>
> + "Pass is healthless. checkForLosslessBitcast should be twin of "<br>
> + "canLosslesslyBitCastTo method, except the case when the last one "<br>
> + "returns false, the first one should return -1 or 1");<br></div>
...<div class=""><br>
> I think we can skip the asserts here. They aren't detecting a specific<br>
> bug, they're checking whether the new code does a certain task relative<br>
> to the old code. Drop the old code, your new code is the new sheriff in<br>
> town.<br></div>
Asserts has been removed.<div class=""><br>
<br>
><br>
> + DenseMap<const Value*, int> sn_map1, sn_map2;<br>
><br>
> What is sn short for ("seen")? Why are there two of these?<br></div>
Serial number :-)<div class=""><br>
><br>
> + std::pair<DenseMap<const Value *, int>::iterator, bool><br>
> + LeftSN = sn_map1.insert(std::make_pair(<u></u>V1, sn_map1.size())),<br>
> + RightSN = sn_map2.insert(std::make_pair(<u></u>V2, sn_map2.size()));<br>
><br>
> So I think I get it, this is easy to reason about. You number each value<br>
> going down both functions. But I think you can eliminate one of these<br>
> maps because you know that if the left and right were ever different<br>
> then we terminate the comparison immediately. You can at least share one<br>
> map with both V1 and V2, but I think you can reduce the number of map<br>
> insertions.<br></div>
Not sure. Consider that in left you have:<br>
%A = alloca i32<br>
%B = alloca i32<br>
store i32 1, i32* %A<br>
<br>
And in right:<br>
%A = alloca i32<br>
%B = alloca i32<br>
store i32 1, i32* %B<br>
<br>
When we meet 'store' instruction we need to check in which order %A was allocated at left and in which order %B was allocated at right.<br>
So for each value in function we have to assign serial number. Then comparing to local values from different functions we can just check their serial numbers.<br>
Though, may be I missed something? May be there is another way to determine "who was first".<div class=""><br>
<br>
> High-level question, are attributes ordered? Your comparison is ordered.<br>
> So if I have function F with string attributes "sse2", "gc=hemisphere"<br>
> and another function G with string attributes "gc=hemisphere", "sse2"<br>
> then they would be considered different. I don't think that's right.<br></div>
I didn't check it. But if it is not ordered, we could order it lexicographically.<div class=""><br>
<br>
><br>
> + int cmpOperation(const Instruction *I1, const Instruction *I2) const;<br>
> +<br>
> bool isEquivalentOperation(const Instruction *I1,<br>
> - const Instruction *I2) const;<br>
> + const Instruction *I2) const {<br>
> + return cmpOperation(I1, I2) == 0;<br>
> + }<br>
><br>
> Hopefully this patch series ultimately eliminates calls of<br>
> isEquivalentOperation?<br></div>
Of course. Just like isEquivalentType.<div class=""><br>
<br>
> By the way, this is an interesting one. Should "add x, y" and "add nsw<br>
> x, y" be equal or not?<br></div>
Yeah. Those are interesting questions. We could even treat 'mul a, 2' and 'shl a,1' as equal in some cases. I think it's matter of time and further optimization.<br>
<br>
Please find first reworked patches in attachment.<br></blockquote><div><br></div><div>I am extremely concerned that you may end up with A < B and B < C but A > C. There are cases where you use cmpTypes to compare two types, then others where you compare them via cmpNumbers. The only way to ensure that the sort function is self-consistent is to be entirely consistent with how we traverse the function.</div>
<div><br></div><div>0001:<br></div><div><div>+ int cmpType(Type *Ty1, Type *Ty2) const;</div><div>+</div></div><div><br></div><div>Please add a comment for this method. Include the meaning of the returned value. ("man strcmp" for inspiration.)</div>
<div><br></div><div>+ static int cmpNumbers(uint64_t L, uint64_t R);<br></div><div><br></div><div>Optional: is there any benefit to making this static instead of a const method? It doesn't need access to the 'this' pointer, but it seems like that's an incidental artifact of the implementation. The other cmp* members are const methods.</div>
<div><br></div><div>+ return cmpNumbers(FTy1->isVarArg(), FTy2->isVarArg());;<br></div><div><br></div><div>Extra semi-colon.</div><div><br></div><div>I trust you to apply the fixes above, you can choose to commit the patch without going through another round of review with me.</div>
<div><br></div><div>0002:<br></div><div><br></div><div>+int FunctionComparator::checkForLosslessBitcast(const Type *L, const Type *R) {<br></div><div>...</div><div>+ int TypesRes = cmpNumbers((uint64_t) L, (uint64_t) R);<br>
</div><div>...</div><div>+ return TypesRes;<br></div><div><br></div><div>Why isn't this using cmpType? Alternatively, any reason not to have cmpPointers(const void *L, const void *R)?</div><div><br></div><div><div>
+ }</div><div>+ else {</div></div><div><br></div><div>Please put the else on the same line as the closing brace.</div><div><br></div><div>+ else if (const VectorType *thisPTy = dyn_cast<VectorType>(L))<br>
</div><div><br></div><div>Missing initial capital, see <a href="http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly">http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly</a> . Also, I find it odd that you switch from "L" and "R" to "this" and "that". Please make those consistent, probably on left and right.</div>
<div><br></div><div>0003:</div><div><br></div><div>+ int cmpConstants(const Constant *L, const Constant *R);<br></div><div><br></div><div>Any reason this method isn't const?</div><div><br></div><div><div>+int FunctionComparator::cmpConstants(const Constant *L, const Constant *R) {</div>
<div>+</div><div>+ // Pack null value as one more Value ID</div><div>+ unsigned LType = L->isNullValue() ? 0 : L->getValueID() + 1;</div><div>+ unsigned RType = R->isNullValue() ? 0 : R->getValueID() + 1;</div>
<div>+</div><div>+ if (int Res = cmpNumbers(LType, RType))</div><div>+ return Res;</div><div>+</div><div>+ if (LType == 0)</div><div>+ return 0;</div><div>+</div><div>+ switch (LType-1) {</div></div><div><br></div>
<div>Optional: how about:</div><div><br></div><div> if (L->isNullValue() && R->isNullValue())</div><div> return cmpType(L->getType(), R->getType());</div><div> if (L->isNullValue() && !R->isNullValue())</div>
<div> return 1;</div><div> if (!L->isNullValue() && R->isNullVaue())</div><div> return -1;</div><div><br></div><div> if (int Res = cmpNumbers(L->getValueID(), R->getValueID()))</div><div> return Res;</div>
<div><br></div><div> switch (L->getValueID()) {</div><div><br></div><div>? In particular I'm not a fan of how LType/RType are equal to valueID+1, even with the comment.</div><div><br></div><div><div>+ case Value::FunctionVal:</div>
<div>+ case Value::GlobalVariableVal:</div><div>+ case Value::GlobalAliasVal:</div><div>+ default: // Unknown constant</div><div>+ return cmpNumbers((uint64_t)L, (uint64_t)R);</div></div><div><br></div><div>Please assert on unknown constant.</div>
<div><br></div><div>How are function, global variable and alias reachable here?</div><div><br></div><div><div>0004:<br></div></div><div><br></div><div>Thanks for the comment on sn_mapL/R!</div><div><br></div><div>+int FunctionComparator::cmpEnumerate(const Value *V1, const Value *V2) {<br>
</div><div><br></div><div>"Compare enumerate"? This name doesn't make sense to me. "cmpValue" perhaps?</div><div><br></div><div><div><div>+ const Constant *C1 = dyn_cast<Constant>(V1);</div>
<div>+ const Constant *C2 = dyn_cast<Constant>(V2);</div><div>+ if (C1 && C2) {</div><div>+ if (V1 == V2) return 0;</div><div> // TODO: constant expressions with GEP or references to F1 or F2.</div>
<div>- if (C1->isNullValue() && C2->isNullValue() &&</div><div>- isEquivalentType(C1->getType(), C2->getType()))</div><div>- return true;</div><div>- // Try bitcasting C2 to C1's type. If the bitcast is legal and returns C1</div>
<div>- // then they must have equal bit patterns.</div><div>- return checkForLosslessBitcast(C1->getType(), C2->getType()) == 0 &&</div><div>- cmpConstants(C1, C2) == 0;</div><div>+ if (C1->isNullValue() && C2->isNullValue()) {</div>
<div>+ if (int Res = cmpType(C1->getType(), C2->getType()))</div><div>+ return Res;</div><div>+ }</div><div>+</div><div>+ // Check whether C2 and C1 has equal bit patterns.</div><div>+ if (int Res = checkForLosslessBitcast(C1->getType(), C2->getType()))</div>
<div>+ return Res;</div><div>+</div><div>+ // Compare C1 and the bitcast result.</div><div>+ if (int Res = cmpConstants(C1, C2))</div><div>+ return Res;</div><div>+</div><div>+ return 0;</div><div> }</div>
</div></div><div><div> </div><div>+ if (C1)</div><div>+ return -1;</div><div>+ if (C2)</div><div>+ return 1;</div></div><div><br></div><div>I'm confused why this isn't just using cmpConstants? I think the isNullValue to cmpType check is already in cmpConstants, why not move the checkForLosslessBitcast there? Is cmpConstants used from elsewhere and needs to not have that check?</div>
<div><br></div><div><div><div><div>+ std::pair<DenseMap<const Value *, int>::iterator, bool></div><div>+ LeftSN = sn_mapL.insert(std::make_pair(V1, sn_mapL.size())),</div><div>+ RightSN = sn_mapR.insert(std::make_pair(V2, sn_mapR.size()));</div>
</div><div><br></div><div>"auto"?</div></div></div><div><br></div><div>0005:</div><div><br></div><div>Okay, this makes attributes ordered.</div><div><br></div><div><div>+ enum AttrType {</div><div>+ Enum,</div>
<div>+ Align,</div><div>+ Other</div><div>+ } LeftAttrType = Other, RightAttrType = Other;</div><div>+</div><div>+ if (LA.isAlignAttribute()) LeftAttrType = Align;</div><div>+ else if (LA.isEnumAttribute()) LeftAttrType = Enum;</div>
<div>+ if (RA.isAlignAttribute()) RightAttrType = Align;</div><div>+ else if (RA.isEnumAttribute()) RightAttrType = Enum;</div><div>+</div><div>+ if (int Res = cmpNumbers(LeftAttrType, RightAttrType))</div>
<div>+ return Res;</div><div>+</div><div>+ switch (LeftAttrType) {</div><div>+ case Enum:</div><div>+ if (int Res = cmpNumbers(LA.getKindAsEnum(), RA.getKindAsEnum()))</div><div>+ return Res;</div>
<div>+ break;</div><div>+ case Align:</div><div>+ if (int Res = cmpNumbers(LA.getValueAsInt(), RA.getValueAsInt()))</div><div>+ return Res;</div><div>+ break;</div><div>+ case Other:</div>
<div>+ if (int Res = cmpStrings(LA.getKindAsString(), RA.getKindAsString()))</div><div>+ return Res;</div><div>+ if (int Res = cmpStrings(LA.getValueAsString(), RA.getValueAsString()))</div><div>+ return Res;</div>
<div>+ break;</div><div>+ }</div></div><div><br></div><div>Attributes already have operator< and operator==. Please reuse them.</div><div><br></div><div>0006:</div><div><br></div><div>This looks fine.</div>
<div><br></div><div>0007:</div><div><br></div><div><div>+ int cmpGEP(const GEPOperator *GEP1, const GEPOperator *GEP2);</div><div>+ int cmpGEP(const GetElementPtrInst *GEP1,</div><div>+ const GetElementPtrInst *GEP2) {</div>
</div><div><br></div><div>Const members?</div><div><br></div><div><div>+ unsigned BitWidth = DL ? DL->getPointerSizeInBits(AS1) : 1;</div><div>+ APInt Offset1(BitWidth, 0), Offset2(BitWidth, 0);</div><div>+ if (DL &&</div>
<div>+ (GEP1->accumulateConstantOffset(*DL, Offset1) &&</div><div>+ GEP2->accumulateConstantOffset(*DL, Offset2)))</div><div>+ return cmpAPInt(Offset1, Offset2);</div></div><div><br></div><div>
I think you should put this under if (DL) { /* declare Offset1, Offset2, etc. */ }</div><div><br></div><div>0008:</div><div><br></div><div>+ // TODO: Already checked in cmpOps<br></div><div><br></div><div>Did you mean "cmpOperation"?</div>
<div><br></div><div><div>- if (!enumerate(F1BB, F2BB) || !compare(F1BB, F2BB))</div><div>+ if (!enumerate(F1BB, F2BB) || compare(F1BB, F2BB) != 0)</div></div><div><br></div><div>"compare" still returns "bool". I'm going to assume this was meant to go in 0009.</div>
<div><br></div><div>0009:</div><div><br></div><div>Looks fine.</div><div><br></div><div>0010: not reviewing this now.</div><div><br></div><div>0011:</div><div><br></div><div>Yay!</div><div><br></div><div>0012:</div><div>
<br>
</div><div>+ typedef std::set<FunctionPtr> FnTreeType;<br></div><div><br></div><div>std::set is frowned upon, see <a href="http://llvm.org/docs/ProgrammersManual.html#set">http://llvm.org/docs/ProgrammersManual.html#set</a> . Do you actually rely on the stable iterator guarantee? Or would another set-like container be a better fit?</div>
<div><br></div><div>+ FunctionPtr(Function *_F, const DataLayout *_DL) : F(_F), DL(_DL) {}<br></div><div><br></div><div>No. An identifier with underscore then capital letter is reserved for the implementation. You can just call them "F" and "DL", then the ctor initializer list can be "F(F), DL(DL)" and that will work fine.</div>
<div><br></div><div>0013:</div><div><br></div><div>+// a ² a (reflexivity)<br></div><div><br></div><div>I'm seeing a "squared" between the two 'a's. Could you represent this in plain ASCII?</div><div>
<br></div><div>+// Comparison iterates through each instruction in each basic block.<br></div><div><br></div><div>Two spaces before "iterates" should be one.</div><div><br></div><div>+// While ability to deal with complex references could be really perspective.<br>
</div><div><br></div><div>Sorry, I'm not sure what this sentence means? The thing your example is talking about is showing is that two functions in an SCC may be equivalent, and detecting them requires "blinding" (ignoring) certain details of the function when you do the comparison. We blind ourselves to the pointee types, but not to callees of functions in the same SCC.</div>
<div><br></div><div>0014:</div><div><br></div><div>Yay again!</div><div><br></div><div><br></div><div>After reading through this patch series, I feel like I'm missing something important. Where's the sort function? It looks like we're still comparing all functions to all other functions.</div>
<div><br></div><div>Nick</div><div><br></div></div></div></div>