[LLVMdev] MergeFunctions: reduce complexity to O(log(N))

[Stepan Dyatkovskiy]

Hi Nick,
I have committed 0001 as r203788.
I'm working on fixes for 0002 - 0014.

 > 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.
When you insert functions into std::set or its analogs it does all the 
job for you. Since internally it builds a binary tree using "less" 
comparison, and each insert/look-up operation takes O(log(N)) time.

-Stepan.

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