[SCEV] Optimize FoldID

[vitalybuka]

Summary

Improve compile time

https://llvm-compile-time-tracker.com/compare.php?from=773e5dfbc6bf4d4c5be568a039661e9baad80d15&to=7ba15f3a4b59181110e73dc397a9fe56165a2b73&stat=instructions:u

[vitalybuka]

fix rebase conflicts

[vitalybuka]

another rebase conflict

[vitalybuka]

clang-format

[vitalybuka]

rebase

[vitalybuka]

This one still improves on top of D144382.

[vitalybuka]

simplify

[vitalybuka]

In D144335#4173558, @vitalybuka wrote:

simplify

@fhahn
is there a reason not to commit this?

[nikic]

I believe the idea behind FoldID was to allow extending it to other SCEV types in the future. That said, I don't think we have specific plans for this right now, so it may makes sense to specialize to the types we're currently interested in.

[vitalybuka]

rebase

[vitalybuka]

ping

[vitalybuka]

ping

[MaskRay]

LGTM.

llvm/include/llvm/Analysis/ScalarEvolution.h

bool loopHasNoAbnormalExits(const Loop *L) {
     return getLoopProperties(L).HasNoAbnormalExits;
   }
 
   /// Return true if this loop is finite by assumption.  That is,
   /// to be infinite, it must also be undefined.
   bool loopIsFiniteByAssumption(const Loop *L);
 
   class FoldID {
-    SmallVector<unsigned, 5> Bits;
+    const SCEV *Op = nullptr;
+    const Type *Ty = nullptr;
+    unsigned short C;
 
   public:
-    void addInteger(unsigned long I) {
-      if (sizeof(long) == sizeof(int))
-        addInteger(unsigned(I));
-      else if (sizeof(long) == sizeof(long long))
-        addInteger((unsigned long long)I);
-      else
-        llvm_unreachable("unexpected sizeof(long)");
-    }
-    void addInteger(unsigned I) { Bits.push_back(I); }
-    void addInteger(int I) { Bits.push_back(I); }
-
-    void addInteger(unsigned long long I) {
-      addInteger(unsigned(I));
-      addInteger(unsigned(I >> 32));
-    }
-
-    void addPointer(const void *Ptr) {
-      // Note: this adds pointers to the hash using sizes and endianness that
-      // depend on the host. It doesn't matter, however, because hashing on
-      // pointer values is inherently unstable. Nothing should depend on the
-      // ordering of nodes in the folding set.
-      static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long),
-                    "unexpected pointer size");
-      addInteger(reinterpret_cast<uintptr_t>(Ptr));
+    FoldID(SCEVTypes C, const SCEV *Op, const Type *Ty) : Op(Op), Ty(Ty), C(C) {
+      assert(Op);
+      assert(Ty);
     }
 
+    FoldID(unsigned short C) : C(C) {}
+
     unsigned computeHash() const {
-      unsigned Hash = Bits.size();
-      for (unsigned I = 0; I != Bits.size(); ++I)
-        Hash = detail::combineHashValue(Hash, Bits[I]);
-      return Hash;
+      return detail::combineHashValue(
+          C, detail::combineHashValue(reinterpret_cast<uintptr_t>(Op),
+                                      reinterpret_cast<uintptr_t>(Ty)));
     }
+
     bool operator==(const FoldID &RHS) const {
-      if (Bits.size() != RHS.Bits.size())
-        return false;
-      for (unsigned I = 0; I != Bits.size(); ++I)
-        if (Bits[I] != RHS.Bits[I])
-          return false;
-      return true;
+      return std::tie(Op, Ty, C) == std::tie(RHS.Op, RHS.Ty, RHS.C);
     }
   };
 
 private:
   /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
   /// Value is deleted.
   class SCEVCallbackVH final : public CallbackVH {
     ScalarEvolution *SE;
private:
   unsigned Generation = 0;
 
   /// The backedge taken count.
   const SCEV *BackedgeCount = nullptr;
 };
 
 template <> struct DenseMapInfo<ScalarEvolution::FoldID> {
   static inline ScalarEvolution::FoldID getEmptyKey() {
-    ScalarEvolution::FoldID ID;
-    ID.addInteger(~0ULL);
+    ScalarEvolution::FoldID ID(0);
     return ID;
   }
   static inline ScalarEvolution::FoldID getTombstoneKey() {
-    ScalarEvolution::FoldID ID;
-    ID.addInteger(~0ULL - 1ULL);
+    ScalarEvolution::FoldID ID(1);
     return ID;
   }
 
   static unsigned getHashValue(const ScalarEvolution::FoldID &Val) {
     return Val.computeHash();
   }
 
   static bool isEqual(const ScalarEvolution::FoldID &LHS,
                       const ScalarEvolution::FoldID &RHS) {
     return LHS == RHS;
   }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_SCALAREVOLUTION_H

llvm/lib/Analysis/ScalarEvolution.cpp

 ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
          "This is not an extending conversion!");
   assert(isSCEVable(Ty) &&
          "This is not a conversion to a SCEVable type!");
   assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
   Ty = getEffectiveSCEVType(Ty);
 
-  FoldID ID;
-  ID.addInteger(scZeroExtend);
-  ID.addPointer(Op);
-  ID.addPointer(Ty);
+  FoldID ID(scZeroExtend, Op, Ty);
   auto Iter = FoldCache.find(ID);
   if (Iter != FoldCache.end())
     return Iter->second;
 
   const SCEV *S = getZeroExtendExprImpl(Op, Ty, Depth);
   if (!isa<SCEVZeroExtendExpr>(S))
     insertFoldCacheEntry(ID, S, FoldCache, FoldCacheUser);
   return S;

 ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
          "This is not an extending conversion!");
   assert(isSCEVable(Ty) &&
          "This is not a conversion to a SCEVable type!");
   assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
   Ty = getEffectiveSCEVType(Ty);
 
-  FoldID ID;
-  ID.addInteger(scSignExtend);
-  ID.addPointer(Op);
-  ID.addPointer(Ty);
+  FoldID ID(scSignExtend, Op, Ty);
   auto Iter = FoldCache.find(ID);
   if (Iter != FoldCache.end())
     return Iter->second;
 
   const SCEV *S = getSignExtendExprImpl(Op, Ty, Depth);
   if (!isa<SCEVSignExtendExpr>(S))
     insertFoldCacheEntry(ID, S, FoldCache, FoldCacheUser);
   return S;