[EarlyCSE] Simplify target intrinsic support

[reames]

Summary

This change unwinds some complexity from the target intrinsic support. Specifically, it removes the idea of an 'ExpectedType'. While we do need to check the type of the returned value (or insert a bitcast), the amount of code involved in the original implementation was a bit excessive. Note that this version may end up doing slightly more work for target intrinsics (due to the lack of an early bail), but tuning for this rare case at the cost of extra complexity seems questionable.

This change also sets us up for a possible followup enhancement to EarlyCSE. Today, we only consider exact SSA equality in the aliasing decisions made by EarlyCSE. We could potentially extend this by stripping bitcasts off the pointer operands and bitcasting the results if needed. Note that this will be necessary once we get typeless/opaque pointers plumbed through everywhere anyways.

Let me ask a basic question. *Why* do we need these target intrinsics at all? Additionally, if we need them, why can't they be expressed as struct stores since that appears to what they represent? Finally, why did we decide to put these in EarlyCSE instead of GVN? (For context, the original review thread is here: http://reviews.llvm.org/D7121)

[ssijaric]

Hi Philip,

The intrinsics that were initially commoned in the original patch were AArch64 intrinsics that we generate with Polly. These were strided loads and stores, for which there was no equivalent LLVM IR at the time. The reason for commoning them them in EarlyCSE instead of GVN was that EarlyCSE was able to common the scalar version - it was mostly to keep it consistent that way. We still have one case for which we need GVN to common intrinsics.

Can we incorporate the LoadSite and StoreSite changes that you suggested, after this patch is merged? These are under http://reviews.llvm.org/D8313.

Thanks,
Sanjin

[hfinkel]

Finally, why did we decide to put these in EarlyCSE instead of GVN?

The eventual goal is still consistency between EarlyCSE and GVN here. Now that MemorySSA is arriving and our GVN will be rewritten, we'll have an opportunity to get convergence.

Additionally, if we need them, why can't they be expressed as struct stores since that appears to what they represent?

In general, I don't think that stores of structures is a good model here. They're swizzled stores (some permutation, xoring, etc. of the data is applied).

This change unwinds some complexity from the target intrinsic support. Specifically, it removes the idea of an 'ExpectedType'. While we do need to check the type of the returned value (or insert a bitcast), the amount of code involved in the original implementation was a bit excessive. Note that this version may end up doing slightly more work for target intrinsics (due to the lack of an early bail), but tuning for this rare case at the cost of extra complexity seems questionable.

The code being removed here does not seem excessive ;) -- I don't see the benefit of removing the 'ExpectedType' parameter. It will cause us to speculatively create new IR instructions. This is not really a matter of tuning, consensus seems to be that we avoid speculatively creating IR instructions whenever possible. Am I missing something?

include/llvm/Analysis/TargetTransformInfo.h

public:
   /// or read to memory, volatility and the pointer.  Info is undefined
   /// if false is returned.
   bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info) const;
 
   /// \returns A value which is the result of the given memory intrinsic.  New
   /// instructions may be created to extract the result from the given intrinsic
   /// memory operation.  Returns nullptr if the target cannot create a result
   /// from the given intrinsic.
-  Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst,
-                                           Type *ExpectedType) const;
+  Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst) const;
 
   /// \returns True if the two functions have compatible attributes for inlining
   /// purposes.
   bool areInlineCompatible(const Function *Caller,
                            const Function *Callee) const;
 
   /// @}
 
virtual int getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
                                     ArrayRef<Type *> Tys) = 0;
   virtual int getCallInstrCost(Function *F, Type *RetTy,
                                ArrayRef<Type *> Tys) = 0;
   virtual unsigned getNumberOfParts(Type *Tp) = 0;
   virtual int getAddressComputationCost(Type *Ty, bool IsComplex) = 0;
   virtual unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) = 0;
   virtual bool getTgtMemIntrinsic(IntrinsicInst *Inst,
                                   MemIntrinsicInfo &Info) = 0;
-  virtual Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst,
-                                                   Type *ExpectedType) = 0;
+  virtual Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst) = 0;
   virtual bool areInlineCompatible(const Function *Caller,
                                    const Function *Callee) const = 0;
 };
 
 template <typename T>
 class TargetTransformInfo::Model final : public TargetTransformInfo::Concept {
   T Impl;
 
public:
   }
   unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) override {
     return Impl.getCostOfKeepingLiveOverCall(Tys);
   }
   bool getTgtMemIntrinsic(IntrinsicInst *Inst,
                           MemIntrinsicInfo &Info) override {
     return Impl.getTgtMemIntrinsic(Inst, Info);
   }
-  Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst,
-                                           Type *ExpectedType) override {
-    return Impl.getOrCreateResultFromMemIntrinsic(Inst, ExpectedType);
+  Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst) override {
+    return Impl.getOrCreateResultFromMemIntrinsic(Inst);
   }
   bool areInlineCompatible(const Function *Caller,
                            const Function *Callee) const override {
     return Impl.areInlineCompatible(Caller, Callee);
   }
 };
 
 template <typename T>

include/llvm/Analysis/TargetTransformInfoImpl.h

public:
   unsigned getReductionCost(unsigned, Type *, bool) { return 1; }
 
   unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) { return 0; }
 
   bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info) {
     return false;
   }
 
-  Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst,
-                                           Type *ExpectedType) {
+  Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst) {
     return nullptr;
   }
 
   bool areInlineCompatible(const Function *Caller,
                            const Function *Callee) const {
     return (Caller->getFnAttribute("target-cpu") ==
             Callee->getFnAttribute("target-cpu")) &&
            (Caller->getFnAttribute("target-features") ==

lib/Analysis/TargetTransformInfo.cpp

 }
 
 bool TargetTransformInfo::getTgtMemIntrinsic(IntrinsicInst *Inst,
                                              MemIntrinsicInfo &Info) const {
   return TTIImpl->getTgtMemIntrinsic(Inst, Info);
 }
 
 Value *TargetTransformInfo::getOrCreateResultFromMemIntrinsic(
-    IntrinsicInst *Inst, Type *ExpectedType) const {
-  return TTIImpl->getOrCreateResultFromMemIntrinsic(Inst, ExpectedType);
+    IntrinsicInst *Inst) const {
+  return TTIImpl->getOrCreateResultFromMemIntrinsic(Inst);
 }
 
 bool TargetTransformInfo::areInlineCompatible(const Function *Caller,
                                               const Function *Callee) const {
   return TTIImpl->areInlineCompatible(Caller, Callee);
 }
 
 TargetTransformInfo::Concept::~Concept() {}

lib/Target/AArch64/AArch64TargetTransformInfo.h

public:
 
   int getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
                       unsigned AddressSpace);
 
   int getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys);
 
   void getUnrollingPreferences(Loop *L, TTI::UnrollingPreferences &UP);
 
-  Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst,
-                                           Type *ExpectedType);
+  Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst);
 
   bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info);
 
   int getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy, unsigned Factor,
                                  ArrayRef<unsigned> Indices, unsigned Alignment,
                                  unsigned AddressSpace);
   /// @}
 };
 
 } // end namespace llvm
 
 #endif

lib/Target/AArch64/AArch64TargetTransformInfo.cpp

void AArch64TTIImpl::getUnrollingPreferences(Loop *L,
   // a larger threshold to unroll more loops.
   if (L->getLoopDepth() > 1)
     UP.PartialThreshold *= 2;
 
   // Disable partial & runtime unrolling on -Os.
   UP.PartialOptSizeThreshold = 0;
 }
 
-Value *AArch64TTIImpl::getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst,
-                                                         Type *ExpectedType) {
+Value *AArch64TTIImpl::getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst) {
   switch (Inst->getIntrinsicID()) {
   default:
     return nullptr;
   case Intrinsic::aarch64_neon_st2:
   case Intrinsic::aarch64_neon_st3:
   case Intrinsic::aarch64_neon_st4: {
-    // Create a struct type
-    StructType *ST = dyn_cast<StructType>(ExpectedType);
-    if (!ST)
-      return nullptr;
     unsigned NumElts = Inst->getNumArgOperands() - 1;
-    if (ST->getNumElements() != NumElts)
-      return nullptr;
-    for (unsigned i = 0, e = NumElts; i != e; ++i) {
-      if (Inst->getArgOperand(i)->getType() != ST->getElementType(i))
-        return nullptr;
-    }
-    Value *Res = UndefValue::get(ExpectedType);
+    SmallVector<Type *, 4> ElementTypes;
+    ElementTypes.reserve(NumElts);
+    for (unsigned i = 0; i < NumElts; ++i)
+      ElementTypes.push_back(Inst->getArgOperand(i)->getType());
+    auto *ST = StructType::get(Inst->getContext(), ElementTypes);
+
+    // FIXME: The need to generate new IR here is unfortunate.  One consequence
+    // of this is that EarlyCSE's trivial writeback DSE will never kick in
+    // since the resulting value will never be pointer equivelent to an
+    // existing one. 
+    Value *Res = UndefValue::get(ST);
     IRBuilder<> Builder(Inst);
     for (unsigned i = 0, e = NumElts; i != e; ++i) {
       Value *L = Inst->getArgOperand(i);
       Res = Builder.CreateInsertValue(Res, L, i);
     }
     return Res;
   }
   case Intrinsic::aarch64_neon_ld2:
   case Intrinsic::aarch64_neon_ld3:
   case Intrinsic::aarch64_neon_ld4:
-    if (Inst->getType() == ExpectedType)
-      return Inst;
-    return nullptr;
   }
 }
 
 bool AArch64TTIImpl::getTgtMemIntrinsic(IntrinsicInst *Inst,
                                         MemIntrinsicInfo &Info) {
   switch (Inst->getIntrinsicID()) {
   default:
     break;

lib/Transforms/Scalar/EarlyCSE.cpp

private:
   private:
     bool IsTargetMemInst;
     MemIntrinsicInfo Info;
     Instruction *Inst;
   };
 
   bool processNode(DomTreeNode *Node);
 
-  Value *getOrCreateResult(Value *Inst, Type *ExpectedType) const {
+  /// Return the value being stored to or loaded from memory.  Note that the
+  /// result type may differ from the pointee type of the pointer operand.
+  /// This is already true of target intrinsics, but will become true for
+  /// normal stores and loads as well once typeless pointers are pushed through
+  /// the IR.  Also note that this routine may end up generating new IR
+  /// immediately before 'Inst' (for target intrinsics).
+  Value *getOrCreateResult(Value *Inst) const {
     if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
       return LI;
     else if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
       return SI->getValueOperand();
-    assert(isa<IntrinsicInst>(Inst) && "Instruction not supported");
-    return TTI.getOrCreateResultFromMemIntrinsic(cast<IntrinsicInst>(Inst),
-                                                 ExpectedType);
+    auto *II = cast<IntrinsicInst>(Inst);
+    return TTI.getOrCreateResultFromMemIntrinsic(II);
   }
 };
 }
 
 bool EarlyCSE::processNode(DomTreeNode *Node) {
   BasicBlock *BB = Node->getBlock();
 
   // If this block has a single predecessor, then the predecessor is the parent
if (MemInst.isValid() && MemInst.isLoad()) {
       // generation, replace this instruction.
       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
       if (InVal.Data != nullptr && InVal.Generation == CurrentGeneration &&
           InVal.MatchingId == MemInst.getMatchingId() &&
           // We don't yet handle removing loads with ordering of any kind.
           !MemInst.isVolatile() && MemInst.isUnordered() &&
           // We can't replace an atomic load with one which isn't also atomic.
           InVal.IsAtomic >= MemInst.isAtomic()) {
-        Value *Op = getOrCreateResult(InVal.Data, Inst->getType());
-        if (Op != nullptr) {
+        Value *Op = getOrCreateResult(InVal.Data);
+        if (Op != nullptr && Op->getType() == Inst->getType()) {
           DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst
                        << "  to: " << *InVal.Data << '\n');
           if (!Inst->use_empty())
             Inst->replaceAllUsesWith(Op);
           Inst->eraseFromParent();
           Changed = true;
           ++NumCSELoad;
           continue;
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     // write back DSE - If we write back the same value we just loaded from
     // the same location and haven't passed any intervening writes or ordering
     // operations, we can remove the write.  The primary benefit is in allowing
     // the available load table to remain valid and value forward past where
     // the store originally was.
     if (MemInst.isValid() && MemInst.isStore()) {
       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
       if (InVal.Data &&
-          InVal.Data == getOrCreateResult(Inst, InVal.Data->getType()) &&
+          InVal.Data == getOrCreateResult(Inst) &&
           InVal.Generation == CurrentGeneration &&
           InVal.MatchingId == MemInst.getMatchingId() &&
           // We don't yet handle removing stores with ordering of any kind.
           !MemInst.isVolatile() && MemInst.isUnordered()) {
         assert((!LastStore ||
                 ParseMemoryInst(LastStore, TTI).getPointerOperand() ==
                 MemInst.getPointerOperand()) &&
                "can't have an intervening store!");