Separate invariant equivalence classes by type

[jdoerfert]

Summary

This reverts r260023.

[grosser]

Hi Johannes,

thank you for fixing this. The changes look good to me, but it would be great if you could update the comments and possibly add 2-3 sentences in the commit message to make it easier for people to get the context of this change.

Best,
Tobias

include/polly/CodeGen/IslNodeBuilder.h

212

Maybe mention this in the comment?

include/polly/ScopInfo.h

857

The comment seems to still need an update.

[jdoerfert]

Commited in r260045.

include/polly/CodeGen/IslNodeBuilder.h

protected:
   /// to its child. This is currently the only behavior implemented, as there is
   /// currently not special handling for marker nodes implemented.
   ///
   /// @param Mark The node we generate code for.
   virtual void createMark(__isl_take isl_ast_node *Marker);
   virtual void createFor(__isl_take isl_ast_node *For);
 
   /// @brief Set to remember materialized invariant loads.
-  SmallPtrSet<const SCEV *, 16> PreloadedPtrs;
+  SmallSet<std::pair<const SCEV *, Type *>, 16> PreloadedPtrs;
 
   /// @brief Preload the memory access at @p AccessRange with @p Build.
   ///
   /// @returns The preloaded value casted to type @p Ty
   Value *preloadUnconditionally(__isl_take isl_set *AccessRange,
                                 isl_ast_build *Build, Instruction *AccInst);
 
   /// @brief Preload the memory load access @p MA.

include/polly/ScopInfo.h

 ///
 /// The first element is the SCEV for the pointer/location that identifies this
 /// equivalence class. The second is a list of memory accesses to that location
 /// that are now treated as invariant and hoisted during code generation. The
 /// last element is the execution context under which the invariant memory
 /// location is accessed, hence the union of all domain contexts for the memory
 /// accesses in the list.
 using InvariantEquivClassTy =
-    std::tuple<const SCEV *, MemoryAccessList, isl_set *>;
+    std::tuple<const SCEV *, MemoryAccessList, isl_set *, Type *>;
 
 /// @brief Type for invariant accesses equivalence classes.
 using InvariantEquivClassesTy = SmallVector<InvariantEquivClassTy, 8>;
 
 ///===----------------------------------------------------------------------===//
 /// @brief Statement of the Scop
 ///
 /// A Scop statement represents an instruction in the Scop.

lib/Analysis/ScopInfo.cpp

UserContext =
                            isl_space_get_dim_id(Space, isl_dim_param, i));
   }
 
   Context = isl_set_intersect(Context, UserContext);
   isl_space_free(Space);
 }
 
 void Scop::buildInvariantEquivalenceClasses() {
-  DenseMap<const SCEV *, LoadInst *> EquivClasses;
+  DenseMap<std::pair<const SCEV *, Type *>, LoadInst *> EquivClasses;
 
   const InvariantLoadsSetTy &RIL = *SD.getRequiredInvariantLoads(&getRegion());
   for (LoadInst *LInst : RIL) {
     const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
 
-    LoadInst *&ClassRep = EquivClasses[PointerSCEV];
+    Type *Ty = LInst->getType();
+    LoadInst *&ClassRep = EquivClasses[std::make_pair(PointerSCEV, Ty)];
     if (ClassRep) {
       InvEquivClassVMap[LInst] = ClassRep;
       continue;
     }
 
     ClassRep = LInst;
-    InvariantEquivClasses.emplace_back(PointerSCEV, MemoryAccessList(),
-                                       nullptr);
+    InvariantEquivClasses.emplace_back(PointerSCEV, MemoryAccessList(), nullptr,
+                                       Ty);
   }
 }
 
 void Scop::buildContext() {
   isl_space *Space = isl_space_params_alloc(IslCtx, 0);
   Context = isl_set_universe(isl_space_copy(Space));
   AssumedContext = isl_set_universe(Space);
 }

 const InvariantEquivClassTy *Scop::lookupInvariantEquivClass(Value *Val) const {
   LoadInst *LInst = dyn_cast<LoadInst>(Val);
   if (!LInst)
     return nullptr;
 
   if (Value *Rep = InvEquivClassVMap.lookup(LInst))
     LInst = cast<LoadInst>(Rep);
 
+  Type *Ty = LInst->getType();
   const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
   for (auto &IAClass : InvariantEquivClasses)
-    if (PointerSCEV == std::get<0>(IAClass))
+    if (PointerSCEV == std::get<0>(IAClass) && Ty == std::get<3>(IAClass))
       return &IAClass;
 
   return nullptr;
 }
 
 void Scop::addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs) {
 
   // Get the context under which the statement is executed.
for (MemoryAccess *MA : InvMAs) {
     }
   }
 
   for (MemoryAccess *MA : InvMAs) {
     // Check for another invariant access that accesses the same location as
     // MA and if found consolidate them. Otherwise create a new equivalence
     // class at the end of InvariantEquivClasses.
     LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
+    Type *Ty = LInst->getType();
     const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
 
     bool Consolidated = false;
     for (auto &IAClass : InvariantEquivClasses) {
-      if (PointerSCEV != std::get<0>(IAClass))
+      if (PointerSCEV != std::get<0>(IAClass) || Ty != std::get<3>(IAClass))
         continue;
 
       Consolidated = true;
 
       // Add MA to the list of accesses that are in this class.
       auto &MAs = std::get<1>(IAClass);
       MAs.push_front(MA);
 
       // Unify the execution context of the class and this statement.
       isl_set *&IAClassDomainCtx = std::get<2>(IAClass);
       if (IAClassDomainCtx)
         IAClassDomainCtx = isl_set_coalesce(
             isl_set_union(IAClassDomainCtx, isl_set_copy(DomainCtx)));
       else
         IAClassDomainCtx = isl_set_copy(DomainCtx);
       break;
     }
 
     if (Consolidated)
       continue;
 
     // If we did not consolidate MA, thus did not find an equivalence class
     // for it, we create a new one.
     InvariantEquivClasses.emplace_back(PointerSCEV, MemoryAccessList{MA},
-                                       isl_set_copy(DomainCtx));
+                                       isl_set_copy(DomainCtx), Ty);
   }
 
   isl_set_free(DomainCtx);
 }
 
 bool Scop::isHoistableAccess(MemoryAccess *Access,
                              __isl_keep isl_union_map *Writes) {
   // TODO: Loads that are not loop carried, hence are in a statement with
bool Scop::isHoistableAccess(MemoryAccess *Access,
 
   // Skip accesses in non-affine subregions as they might not be executed
   // under the same condition as the entry of the non-affine subregion.
   if (BB != Access->getAccessInstruction()->getParent())
     return false;
 
   isl_map *AccessRelation = Access->getAccessRelation();
 
-  // Invariant load hoisting of memory accesses with non-canonical element
-  // types lacks support for equivalence classes that contain elements of
-  // different width/size. Hence, do not yet consider loads with non-canonical
-  // element size for load hoisting.
-  if (!isl_map_is_single_valued(AccessRelation)) {
-    isl_map_free(AccessRelation);
-    return false;
-  }
-
   // Skip accesses that have an empty access relation. These can be caused
   // by multiple offsets with a type cast in-between that cause the overall
   // byte offset to be not divisible by the new types sizes.
   if (isl_map_is_empty(AccessRelation)) {
     isl_map_free(AccessRelation);
     return false;
   }
 

lib/CodeGen/IslNodeBuilder.cpp

bool IslNodeBuilder::preloadInvariantEquivClass(
   // If the access function was already mapped, the preload of this equivalence
   // class was triggered earlier already and doesn't need to be done again.
   if (ValueMap.count(MA->getAccessInstruction()))
     return true;
 
   // Check for recurrsion which can be caused by additional constraints, e.g.,
   // non-finitie loop contraints. In such a case we have to bail out and insert
   // a "false" runtime check that will cause the original code to be executed.
-  if (!PreloadedPtrs.insert(std::get<0>(IAClass)).second)
+  auto PtrId = std::make_pair(std::get<0>(IAClass), std::get<3>(IAClass));
+  if (!PreloadedPtrs.insert(PtrId).second)
     return false;
 
   // If the base pointer of this class is dependent on another one we have to
   // make sure it was preloaded already.
   auto *SAI = MA->getScopArrayInfo();
   if (const auto *BaseIAClass = S.lookupInvariantEquivClass(SAI->getBasePtr()))
     if (!preloadInvariantEquivClass(*BaseIAClass))
       return false;
 
   Instruction *AccInst = MA->getAccessInstruction();
   Type *AccInstTy = AccInst->getType();
 
   isl_set *Domain = isl_set_copy(std::get<2>(IAClass));
   Value *PreloadVal = preloadInvariantLoad(*MA, Domain);
   if (!PreloadVal)
     return false;
 
-  assert(PreloadVal->getType() == AccInst->getType());
   for (const MemoryAccess *MA : MAs) {
     Instruction *MAAccInst = MA->getAccessInstruction();
-    // TODO: The bitcast here is wrong. In case of floating and non-floating
-    //       point values we need to reload the value or convert it.
-    ValueMap[MAAccInst] =
-        Builder.CreateBitOrPointerCast(PreloadVal, MAAccInst->getType());
+    assert(PreloadVal->getType() == MAAccInst->getType());
+    ValueMap[MAAccInst] = PreloadVal;
   }
 
   if (SE.isSCEVable(AccInstTy)) {
     isl_id *ParamId = S.getIdForParam(SE.getSCEV(AccInst));
     if (ParamId)
       IDToValue[ParamId] = PreloadVal;
     isl_id_free(ParamId);
   }
 
   BasicBlock *EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
   auto *Alloca = new AllocaInst(AccInstTy, AccInst->getName() + ".preload.s2a");
   Alloca->insertBefore(&*EntryBB->getFirstInsertionPt());
   Builder.CreateStore(PreloadVal, Alloca);
 
   for (auto *DerivedSAI : SAI->getDerivedSAIs()) {
     Value *BasePtr = DerivedSAI->getBasePtr();
 
     for (const MemoryAccess *MA : MAs) {
       // As the derived SAI information is quite coarse, any load from the
       // current SAI could be the base pointer of the derived SAI, however we
       // should only change the base pointer of the derived SAI if we actually
       // preloaded it.
       if (BasePtr == MA->getBaseAddr()) {
-        // TODO: The bitcast here is wrong. In case of floating and non-floating
-        //       point values we need to reload the value or convert it.
-        BasePtr =
-            Builder.CreateBitOrPointerCast(PreloadVal, BasePtr->getType());
-        DerivedSAI->setBasePtr(BasePtr);
+        assert(BasePtr->getType() == PreloadVal->getType());
+        DerivedSAI->setBasePtr(PreloadVal);
       }
 
       // For scalar derived SAIs we remap the alloca used for the derived value.
       if (BasePtr == MA->getAccessInstruction()) {
         if (DerivedSAI->isPHIKind())
           PHIOpMap[BasePtr] = Alloca;
         else
           ScalarMap[BasePtr] = Alloca;

test/Isl/CodeGen/multiple-types-invariant-load.ll

-; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
-
-; Invariant loads with non-canonical types are not yet fully supported.
-
-; XFAIL: *
+; RUN: opt %loadPolly -polly-allow-differing-element-types -polly-codegen -S < %s | FileCheck %s
 
 ; CHECK: %polly.access.cast.global.load = bitcast %struct.hoge* %global.load to i32*
 ; CHECK: %polly.access.global.load = getelementptr i32, i32* %polly.access.cast.global.load, i64 0
 ; CHECK: %polly.access.global.load.load = load i32, i32* %polly.access.global.load
 
-; CHECK: %polly.access.cast.global.load1 = bitcast %struct.hoge* %global.load to i32*
-; CHECK: %polly.access.global.load2 = getelementptr i32, i32* %polly.access.cast.global.load1, i64 2
-; CHECK: %polly.access.global.load2.cast = bitcast i32* %polly.access.global.load2 to double*
-; CHECK: %polly.access.global.load2.load = load double, double* %polly.access.global.load2.cast
-
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 %struct.hoge = type { i32, double }
 
 @global = external global %struct.hoge*, align 8
 
 ; Function Attrs: nounwind uwtable

test/ScopInfo/invariant_load_access_classes_different_base_type_same_pointer.ll

 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s --check-prefix=CODEGEN
 ;
 ;    int U;
 ;    void f(int *A) {
 ;      for (int i = 0; i < 1000; i++)
 ;        A[i] = (*(int *)&U) + (int)(*(float *)&U);
 ;    }
 ;
 ; CHECK:      Invariant Accesses: {
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             { Stmt_for_body[i0] -> MemRef_U[0] };
 ; CHECK-NEXT:         Execution Context: {  :  }
+; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             { Stmt_for_body[i0] -> MemRef_U[0] };
+; CHECK-NEXT:         Execution Context: {  :  }
 ; CHECK-NEXT: }
 ;
 ; CHECK:      Statements {
 ; CHECK-NEXT:     Stmt_for_body
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             { Stmt_for_body[i0] : 0 <= i0 <= 999 };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             { Stmt_for_body[i0] -> [i0] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             { Stmt_for_body[i0] -> MemRef_A[i0] };
 ; CHECK-NEXT: }
 ;
 ; CODEGEN: entry:
-; CODEGEN:   %U.f.preload.s2a = alloca float
+; CODEGEN-DAG:   %U.f.preload.s2a = alloca float
+; CODEGEN-DAG:   %U.i.preload.s2a = alloca i32
 ; CODEGEN:   br label %polly.split_new_and_old
 ;
 ; CODEGEN: polly.preload.begin:
-; CODEGEN:   %U.load = load float, float* bitcast (i32* @U to float*)
-; CODEGEN:   %0 = bitcast float %U.load to i32
-; CODEGEN:   store float %U.load, float* %U.f.preload.s2a
+; CODEGEN-DAG:   %U.load[[f:[.0-9]*]] = load float, float* bitcast (i32* @U to float*)
+; CODEGEN-DAG:   store float %U.load[[f]], float* %U.f.preload.s2a
+; CODEGEN-DAG:   %U.load[[i:[.0-9]*]] = load i32, i32* @U
+; CODEGEN-DAG:   store i32 %U.load[[i]], i32* %U.i.preload.s2a
 ;
 ; CODEGEN:     polly.merge_new_and_old:
 ; CODEGEN-NOT:   merge = phi
 ;
 ; CODEGEN: polly.loop_exit:
 ; CODEGEN-NOT:   final_reload
 ;
 ; CODEGEN: polly.stmt.for.body:
-; CODEGEN:   %p_conv = fptosi float %U.load to i32
-; CODEGEN:   %p_add = add nsw i32 %0, %p_conv
+; CODEGEN:   %p_add = add nsw i32 %U.load[[i]], %p_conv
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 @U = common global i32 0, align 4
 
 define void @f(i32* %A) {
 entry:
   br label %for.cond

test/ScopInfo/invariant_load_access_classes_different_base_type_same_pointer_escaping.ll

 ;      } while (i++ < 100);
 ;      return x + y;
 ;    }
 ;
 ; CHECK:      Invariant Accesses: {
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             { Stmt_do_body[i0] -> MemRef_U[0] };
 ; CHECK-NEXT:         Execution Context: {  :  }
+; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             { Stmt_do_body[i0] -> MemRef_U[0] };
+; CHECK-NEXT:         Execution Context: {  :  }
 ; CHECK-NEXT: }
 ;
 ; CHECK:      Statements {
 ; CHECK-NEXT:     Stmt_do_body
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             { Stmt_do_body[i0] : 0 <= i0 <= 100 };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             { Stmt_do_body[i0] -> [i0] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             { Stmt_do_body[i0] -> MemRef_A[i0] };
 ; CHECK-NEXT: }
 ;
 ; CODEGEN: entry:
-; CODEGEN:   %U.f.preload.s2a = alloca float
+; CODEGEN-DAG:   %U.f.preload.s2a = alloca float
+; CODEGEN-DAG:   %U.i.preload.s2a = alloca i32
 ; CODEGEN:   br label %polly.split_new_and_old
 ;
 ; CODEGEN: polly.preload.begin:
-; CODEGEN:   %U.load = load float, float* bitcast (i32* @U to float*)
-; CODEGEN:   %0 = bitcast float %U.load to i32
-; CODEGEN:   store float %U.load, float* %U.f.preload.s2a
+; CODEGEN-DAG:   %U.load[[f:[.0-9]*]] = load float, float* bitcast (i32* @U to float*)
+; CODEGEN-DAG:   store float %U.load[[f]], float* %U.f.preload.s2a
+; CODEGEN-DAG:   %U.load[[i:[.0-9]*]] = load i32, i32* @U
+; CODEGEN-DAG:   store i32 %U.load[[i]], i32* %U.i.preload.s2a
 ;
 ; CODEGEN:     polly.merge_new_and_old:
 ; CODEGEN-DAG:   %U.f.merge = phi float [ %U.f.final_reload, %polly.exiting ], [ %U.f, %do.cond ]
-; CODEGEN-DAG:   %U.i.merge = phi i32 [ %5, %polly.exiting ], [ %U.i, %do.cond ]
+; CODEGEN-DAG:   %U.i.merge = phi i32 [ %U.i.final_reload, %polly.exiting ], [ %U.i, %do.cond ]
 ;
 ; CODEGEN: polly.loop_exit:
 ; CODEGEN-DAG:   %U.f.final_reload = load float, float* %U.f.preload.s2a
-; CODEGEN-DAG:   %U.i.final_reload = load float, float* %U.f.preload.s2a
-; CODEGEN-DAG:   %5 = bitcast float %U.i.final_reload to i32
+; CODEGEN-DAG:   %U.i.final_reload = load i32, i32* %U.i.preload.s2a
 ;
 ; CODEGEN: polly.stmt.do.body:
-; CODEGEN:   %p_conv = fptosi float %U.load to i32
-; CODEGEN:   %p_add = add nsw i32 %0, %p_conv
+; CODEGEN:   %p_add = add nsw i32 %U.load[[i]], %p_conv
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 @U = common global i32 0, align 4
 
 define i32 @f(i32* %A) {
 entry:
   br label %do.body