From bb6495cc673db919225768a62872b79205a3af41 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sun, 20 Sep 2009 19:03:47 +0000 Subject: [PATCH] enhance GVN to forward substitute a stored value to a load (and load -> load) when the base pointers must alias but when they are different types. This occurs very very frequently in 176.gcc and other code that uses bitfields a lot. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@82399 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/GVN.cpp | 144 ++++++++++++++++++++++++++++++---- test/Transforms/GVN/rle.ll | 119 ++++++++++++++++++++++++++++ 2 files changed, 248 insertions(+), 15 deletions(-) create mode 100644 test/Transforms/GVN/rle.ll diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index c36f5e1791e..d8418ec1ef4 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -39,6 +39,7 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetData.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" #include @@ -1210,19 +1211,106 @@ bool GVN::processNonLocalLoad(LoadInst *LI, return true; } +/// CoerceAvailableValueToLoadType - If we saw a store of a value to memory, and +/// then a load from a must-aliased pointer of a different type, try to coerce +/// the stored value. If we can't do it, return null. +static Value *CoerceAvailableValueToLoadType(Value *StoredVal, LoadInst *L, + const TargetData &TD) { + const Type *StoredValTy = StoredVal->getType(); + const Type *LoadedTy = L->getType(); + + uint64_t StoreSize = TD.getTypeSizeInBits(StoredValTy); + uint64_t LoadSize = TD.getTypeSizeInBits(LoadedTy); + + // If the store and reload are the same size, we can always reuse it. + if (StoreSize == LoadSize) { + if (isa(StoredValTy) && isa(LoadedTy)) { + // Pointer to Pointer -> use bitcast. + return new BitCastInst(StoredVal, LoadedTy, "", L); + } + + // Convert source pointers to integers, which can be bitcast. + if (isa(StoredValTy)) { + StoredValTy = TD.getIntPtrType(StoredValTy->getContext()); + StoredVal = new PtrToIntInst(StoredVal, StoredValTy, "", L); + } + + const Type *TypeToCastTo = LoadedTy; + if (isa(TypeToCastTo)) + TypeToCastTo = TD.getIntPtrType(StoredValTy->getContext()); + + if (StoredValTy != TypeToCastTo) + StoredVal = new BitCastInst(StoredVal, TypeToCastTo, "", L); + + // Cast to pointer if the load needs a pointer type. + if (isa(LoadedTy)) + StoredVal = new IntToPtrInst(StoredVal, LoadedTy, "", L); + + return StoredVal; + } + + // If the loaded value is smaller than the available value, then we can + // extract out a piece from it. If the available value is too small, then we + // can't do anything. + if (StoreSize < LoadSize) + return 0; + + // Convert source pointers to integers, which can be manipulated. + if (isa(StoredValTy)) { + StoredValTy = TD.getIntPtrType(StoredValTy->getContext()); + StoredVal = new PtrToIntInst(StoredVal, StoredValTy, "", L); + } + + // Convert vectors and fp to integer, which can be manipulated. + if (!isa(StoredValTy)) { + StoredValTy = IntegerType::get(StoredValTy->getContext(), StoreSize); + StoredVal = new BitCastInst(StoredVal, StoredValTy, "", L); + } + + // If this is a big-endian system, we need to shift the value down to the low + // bits so that a truncate will work. + if (TD.isBigEndian()) { + Constant *Val = ConstantInt::get(StoredVal->getType(), StoreSize-LoadSize); + StoredVal = BinaryOperator::CreateLShr(StoredVal, Val, "tmp", L); + } + + // Truncate the integer to the right size now. + const Type *NewIntTy = IntegerType::get(StoredValTy->getContext(), LoadSize); + StoredVal = new TruncInst(StoredVal, NewIntTy, "trunc", L); + + if (LoadedTy == NewIntTy) + return StoredVal; + + // If the result is a pointer, inttoptr. + if (isa(LoadedTy)) + return new IntToPtrInst(StoredVal, LoadedTy, "inttoptr", L); + + // Otherwise, bitcast. + return new BitCastInst(StoredVal, LoadedTy, "bitcast", L); +} + + /// processLoad - Attempt to eliminate a load, first by eliminating it /// locally, and then attempting non-local elimination if that fails. bool GVN::processLoad(LoadInst *L, SmallVectorImpl &toErase) { if (L->isVolatile()) return false; - Value* pointer = L->getPointerOperand(); - // ... to a pointer that has been loaded from before... MemDepResult dep = MD->getDependency(L); // If the value isn't available, don't do anything! if (dep.isClobber()) { + // FIXME: In the future, we should handle things like: + // store i32 123, i32* %P + // %A = bitcast i32* %P to i8* + // %B = gep i8* %A, i32 1 + // %C = load i8* %B + // + // We could do that by recognizing if the clobber instructions are obviously + // a common base + constant offset, and if the previous store (or memset) + // completely covers this load. This sort of thing can happen in bitfield + // access code. DEBUG( // fast print dep, using operator<< on instruction would be too slow errs() << "GVN: load "; @@ -1239,28 +1327,50 @@ bool GVN::processLoad(LoadInst *L, SmallVectorImpl &toErase) { Instruction *DepInst = dep.getInst(); if (StoreInst *DepSI = dyn_cast(DepInst)) { - // Only forward substitute stores to loads of the same type. - // FIXME: Could do better! - if (DepSI->getPointerOperand()->getType() != pointer->getType()) - return false; + Value *StoredVal = DepSI->getOperand(0); + + // The store and load are to a must-aliased pointer, but they may not + // actually have the same type. See if we know how to reuse the stored + // value (depending on its type). + const TargetData *TD = 0; + if (StoredVal->getType() != L->getType() && + (TD = getAnalysisIfAvailable())) { + StoredVal = CoerceAvailableValueToLoadType(StoredVal, L, *TD); + if (StoredVal == 0) + return false; + + DEBUG(errs() << "GVN COERCED STORE:\n" << *DepSI << '\n' << *StoredVal + << '\n' << *L << "\n\n\n"); + } // Remove it! - L->replaceAllUsesWith(DepSI->getOperand(0)); - if (isa(DepSI->getOperand(0)->getType())) - MD->invalidateCachedPointerInfo(DepSI->getOperand(0)); + L->replaceAllUsesWith(StoredVal); + if (isa(StoredVal->getType())) + MD->invalidateCachedPointerInfo(StoredVal); toErase.push_back(L); NumGVNLoad++; return true; } if (LoadInst *DepLI = dyn_cast(DepInst)) { - // Only forward substitute stores to loads of the same type. - // FIXME: Could do better! load i32 -> load i8 -> truncate on little endian. - if (DepLI->getType() != L->getType()) - return false; - + Value *AvailableVal = DepLI; + + // The loads are of a must-aliased pointer, but they may not actually have + // the same type. See if we know how to reuse the previously loaded value + // (depending on its type). + const TargetData *TD = 0; + if (DepLI->getType() != L->getType() && + (TD = getAnalysisIfAvailable())) { + AvailableVal = CoerceAvailableValueToLoadType(DepLI, L, *TD); + if (AvailableVal == 0) + return false; + + DEBUG(errs() << "GVN COERCED LOAD:\n" << *DepLI << "\n" << *AvailableVal + << "\n" << *L << "\n\n\n"); + } + // Remove it! - L->replaceAllUsesWith(DepLI); + L->replaceAllUsesWith(AvailableVal); if (isa(DepLI->getType())) MD->invalidateCachedPointerInfo(DepLI); toErase.push_back(L); @@ -1268,6 +1378,10 @@ bool GVN::processLoad(LoadInst *L, SmallVectorImpl &toErase) { return true; } + // FIXME: We should handle memset/memcpy/memmove as dependent instructions to + // forward the value if available. + + // If this load really doesn't depend on anything, then we must be loading an // undef value. This can happen when loading for a fresh allocation with no // intervening stores, for example. diff --git a/test/Transforms/GVN/rle.ll b/test/Transforms/GVN/rle.ll new file mode 100644 index 00000000000..cd3a611128c --- /dev/null +++ b/test/Transforms/GVN/rle.ll @@ -0,0 +1,119 @@ +; RUN: opt < %s -gvn -S | FileCheck %s + +; 32-bit little endian target. +target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128" + +;; Trivial RLE test. +define i32 @test0(i32 %V, i32* %P) { + store i32 %V, i32* %P + + %A = load i32* %P + ret i32 %A +; CHECK: @test0 +; CHECK: ret i32 %V +} + +;;===----------------------------------------------------------------------===;; +;; Store -> Load and Load -> Load forwarding where src and dst are different +;; types, but where the base pointer is a must alias. +;;===----------------------------------------------------------------------===;; + +;; i32 -> f32 forwarding. +define float @coerce_mustalias1(i32 %V, i32* %P) { + store i32 %V, i32* %P + + %P2 = bitcast i32* %P to float* + + %A = load float* %P2 + ret float %A +; CHECK: @coerce_mustalias1 +; CHECK-NOT: load +; CHECK: ret float +} + +;; i32* -> float forwarding. +define float @coerce_mustalias2(i32* %V, i32** %P) { + store i32* %V, i32** %P + + %P2 = bitcast i32** %P to float* + + %A = load float* %P2 + ret float %A +; CHECK: @coerce_mustalias2 +; CHECK-NOT: load +; CHECK: ret float +} + +;; float -> i32* forwarding. +define i32* @coerce_mustalias3(float %V, float* %P) { + store float %V, float* %P + + %P2 = bitcast float* %P to i32** + + %A = load i32** %P2 + ret i32* %A +; CHECK: @coerce_mustalias3 +; CHECK-NOT: load +; CHECK: ret i32* +} + +;; i32 -> f32 load forwarding. +define float @coerce_mustalias4(i32* %P, i1 %cond) { + %A = load i32* %P + br i1 %cond, label %T, label %T +T: + %P2 = bitcast i32* %P to float* + + %B = load float* %P2 + ret float %B + +F: + %X = bitcast i32 %A to float + ret float %X + +; CHECK: @coerce_mustalias4 +; CHECK: %A = load i32* %P +; CHECK-NOT: load +; CHECK: ret float +; CHECK: F: +} + +;; i32 -> i8 forwarding +define i8 @coerce_mustalias5(i32 %V, i32* %P) { + store i32 %V, i32* %P + + %P2 = bitcast i32* %P to i8* + + %A = load i8* %P2 + ret i8 %A +; CHECK: @coerce_mustalias5 +; CHECK-NOT: load +; CHECK: ret i8 +} + +;; i64 -> float forwarding +define float @coerce_mustalias6(i64 %V, i64* %P) { + store i64 %V, i64* %P + + %P2 = bitcast i64* %P to float* + + %A = load float* %P2 + ret float %A +; CHECK: @coerce_mustalias6 +; CHECK-NOT: load +; CHECK: ret float +} + +;; i64 -> i8* (32-bit) forwarding +define i8* @coerce_mustalias7(i64 %V, i64* %P) { + store i64 %V, i64* %P + + %P2 = bitcast i64* %P to i8** + + %A = load i8** %P2 + ret i8* %A +; CHECK: @coerce_mustalias7 +; CHECK-NOT: load +; CHECK: ret i8* +} + -- 2.34.1