This is an archive of the discontinued LLVM Phabricator instance.

Differential D30478

Move memory coercion functions from GVN.cpp to VNCoercion.cpp so they can be shared between GVN and NewGVN.
ClosedPublic

Authored by • dberlin on Feb 28 2017, 3:17 PM.

Details

Reviewers
davide
Commits
rG5ac9179f6ceb: Move memory coercion functions from GVN.cpp to VNCoercion.cpp so they can be…
rL297438: Move memory coercion functions from GVN.cpp to VNCoercion.cpp so they can be…
Summary

These are the functions used to determine when values of loads can be
extracted from stores, etc, and to perform the necessary insertions to
do this. There are no changes to the functions themselves except
reformatting, and one case where memdep was informed of a removed load
(which was pushed into the caller).

Diff Detail

Repository
rL LLVM

Event Timeline

• dberlin created this revision.Feb 28 2017, 3:17 PM
Herald added subscribers: Prazek, mgorny. · View Herald TranscriptFeb 28 2017, 3:17 PM
davide accepted this revision.Mar 5 2017, 3:35 PM

LGTM, with the inline comment addressed. Thanks!

lib/Transforms/Utils/VNCoercion.cpp
1–6 ↗(On Diff #90093)

This probably needs an header comment with the license etc..

This revision is now accepted and ready to land.Mar 5 2017, 3:35 PM
Closed by commit rL297438: Move memory coercion functions from GVN.cpp to VNCoercion.cpp so they can be… (authored by dannyb). · Explain WhyMar 9 2017, 9:06 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
trunk/
include/
llvm/
Transforms/
Utils/
96 lines
lib/
Transforms/
Scalar/
466 lines
Utils/
1 line
440 lines

Diff 91264

llvm/trunk/include/llvm/Transforms/Utils/VNCoercion.h

//===- VNCoercion.h - Value Numbering Coercion Utilities --------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
/// \file / This file provides routines used by LLVM's value numbering passes to
/// perform various forms of value extraction from memory when the types are not
/// identical. For example, given
///
/// store i32 8, i32 *%foo
/// %a = bitcast i32 *%foo to i16
/// %val = load i16, i16 *%a
///
/// It possible to extract the value of the load of %a from the store to %foo.
/// These routines know how to tell whether they can do that (the analyze*
/// routines), and can also insert the necessary IR to do it (the get*
/// routines).
#ifndef LLVM_TRANSFORMS_UTILS_VNCOERCION_H
#define LLVM_TRANSFORMS_UTILS_VNCOERCION_H
#include "llvm/IR/IRBuilder.h"
namespace llvm {
class Function;
class StoreInst;
class LoadInst;
class MemIntrinsic;
class Instruction;
class Value;
class Type;
class DataLayout;
namespace VNCoercion {
/// Return true if CoerceAvailableValueToLoadType would succeed if it was
/// called.
bool canCoerceMustAliasedValueToLoad(Value *StoredVal, Type *LoadTy,
const DataLayout &DL);
/// 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 to the loaded
/// type. LoadedTy is the type of the load we want to replace. IRB is
/// IRBuilder used to insert new instructions.
///
/// If we can't do it, return null.
Value *coerceAvailableValueToLoadType(Value *StoredVal, Type *LoadedTy,
IRBuilder<> &IRB, const DataLayout &DL);
/// This function determines whether a value for the pointer LoadPtr can be
/// extracted from the store at DepSI.
///
/// On success, it returns the offset into DepSI that extraction would start.
/// On failure, it returns -1.
int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr,
StoreInst *DepSI);
/// This function determines whether a value for the pointer LoadPtr can be
/// extracted from the load at DepLI.
///
/// On success, it returns the offset into DepLI that extraction would start.
/// On failure, it returns -1.
int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI,
const DataLayout &DL);
/// This function determines whether a value for the pointer LoadPtr can be
/// extracted from the memory intrinsic at DepMI.
///
/// On success, it returns the offset into DepMI that extraction would start.
/// On failure, it returns -1.
int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr,
MemIntrinsic *DepMI, const DataLayout &DL);
/// If analyzeLoadFromClobberingStore returned an offset, this function can be
/// used to actually perform the extraction of the bits from the store. It
/// inserts instructions to do so at InsertPt, and returns the extracted value.
Value *getStoreValueForLoad(Value *SrcVal, unsigned Offset, Type *LoadTy,
Instruction *InsertPt, const DataLayout &DL);
/// If analyzeLoadFromClobberingLoad returned an offset, this function can be
/// used to actually perform the extraction of the bits from the load, including
/// any necessary load widening. It inserts instructions to do so at InsertPt,
/// and returns the extracted value.
Value *getLoadValueForLoad(LoadInst *SrcVal, unsigned Offset, Type *LoadTy,
Instruction *InsertPt);
/// If analyzeLoadFromClobberingMemInst returned an offset, this function can be
/// used to actually perform the extraction of the bits from the memory
/// intrinsic. It inserts instructions to do so at InsertPt, and returns the
/// extracted value.
Value *getMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset,
Type *LoadTy, Instruction *InsertPt,
const DataLayout &DL);
}
}
#endif

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

Show All 30 Lines
#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/Loads.h" #include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/OptimizationDiagnosticInfo.h" #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
#include "llvm/Analysis/PHITransAddr.h" #include "llvm/Analysis/PHITransAddr.h"
#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DataLayout.h" #include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h" #include "llvm/IR/Dominators.h"
#include "llvm/IR/GlobalVariable.h" #include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IRBuilder.h" #include "llvm/IR/IRBuilder.h"
#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h" #include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h" #include "llvm/IR/Metadata.h"
#include "llvm/IR/PatternMatch.h" #include "llvm/IR/PatternMatch.h"
#include "llvm/Support/CommandLine.h" #include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h" #include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h" #include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SSAUpdater.h" #include "llvm/Transforms/Utils/SSAUpdater.h"
#include "llvm/Transforms/Utils/VNCoercion.h"
#include <vector> #include <vector>
using namespace llvm; using namespace llvm;
using namespace llvm::gvn; using namespace llvm::gvn;
using namespace llvm::VNCoercion;
using namespace PatternMatch; using namespace PatternMatch;
#define DEBUG_TYPE "gvn" #define DEBUG_TYPE "gvn"
STATISTIC(NumGVNInstr, "Number of instructions deleted"); STATISTIC(NumGVNInstr, "Number of instructions deleted");
STATISTIC(NumGVNLoad, "Number of loads deleted"); STATISTIC(NumGVNLoad, "Number of loads deleted");
STATISTIC(NumGVNPRE, "Number of instructions PRE'd"); STATISTIC(NumGVNPRE, "Number of instructions PRE'd");
STATISTIC(NumGVNBlocks, "Number of blocks merged"); STATISTIC(NumGVNBlocks, "Number of blocks merged");
▲ Show 20 Lines • Show All 622 Lines • ▼ Show 20 Lines do {
BBWorklist.append(succ_begin(Entry), succ_end(Entry)); BBWorklist.append(succ_begin(Entry), succ_end(Entry));
} while (!BBWorklist.empty()); } while (!BBWorklist.empty());
return false; return false;
} }
/// Return true if CoerceAvailableValueToLoadType will succeed.
static bool CanCoerceMustAliasedValueToLoad(Value *StoredVal,
Type *LoadTy,
const DataLayout &DL) {
// If the loaded or stored value is an first class array or struct, don't try
// to transform them. We need to be able to bitcast to integer.
if (LoadTy->isStructTy() || LoadTy->isArrayTy() ||
StoredVal->getType()->isStructTy() ||
StoredVal->getType()->isArrayTy())
return false;
// The store has to be at least as big as the load.
if (DL.getTypeSizeInBits(StoredVal->getType()) <
DL.getTypeSizeInBits(LoadTy))
return false;
return true;
}
/// 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. LoadedTy is the type of the load we want to replace.
/// IRB is IRBuilder used to insert new instructions.
///
/// If we can't do it, return null.
static Value *CoerceAvailableValueToLoadType(Value *StoredVal, Type *LoadedTy,
IRBuilder<> &IRB,
const DataLayout &DL) {
assert(CanCoerceMustAliasedValueToLoad(StoredVal, LoadedTy, DL) &&
"precondition violation - materialization can't fail");
if (auto *C = dyn_cast<Constant>(StoredVal))
if (auto *FoldedStoredVal = ConstantFoldConstant(C, DL))
StoredVal = FoldedStoredVal;
// If this is already the right type, just return it.
Type *StoredValTy = StoredVal->getType();
uint64_t StoredValSize = DL.getTypeSizeInBits(StoredValTy);
uint64_t LoadedValSize = DL.getTypeSizeInBits(LoadedTy);
// If the store and reload are the same size, we can always reuse it.
if (StoredValSize == LoadedValSize) {
// Pointer to Pointer -> use bitcast.
if (StoredValTy->getScalarType()->isPointerTy() &&
LoadedTy->getScalarType()->isPointerTy()) {
StoredVal = IRB.CreateBitCast(StoredVal, LoadedTy);
} else {
// Convert source pointers to integers, which can be bitcast.
if (StoredValTy->getScalarType()->isPointerTy()) {
StoredValTy = DL.getIntPtrType(StoredValTy);
StoredVal = IRB.CreatePtrToInt(StoredVal, StoredValTy);
}
Type *TypeToCastTo = LoadedTy;
if (TypeToCastTo->getScalarType()->isPointerTy())
TypeToCastTo = DL.getIntPtrType(TypeToCastTo);
if (StoredValTy != TypeToCastTo)
StoredVal = IRB.CreateBitCast(StoredVal, TypeToCastTo);
// Cast to pointer if the load needs a pointer type.
if (LoadedTy->getScalarType()->isPointerTy())
StoredVal = IRB.CreateIntToPtr(StoredVal, LoadedTy);
}
if (auto *C = dyn_cast<ConstantExpr>(StoredVal))
if (auto *FoldedStoredVal = ConstantFoldConstant(C, DL))
StoredVal = FoldedStoredVal;
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.
assert(StoredValSize >= LoadedValSize &&
"CanCoerceMustAliasedValueToLoad fail");
// Convert source pointers to integers, which can be manipulated.
if (StoredValTy->getScalarType()->isPointerTy()) {
StoredValTy = DL.getIntPtrType(StoredValTy);
StoredVal = IRB.CreatePtrToInt(StoredVal, StoredValTy);
}
// Convert vectors and fp to integer, which can be manipulated.
if (!StoredValTy->isIntegerTy()) {
StoredValTy = IntegerType::get(StoredValTy->getContext(), StoredValSize);
StoredVal = IRB.CreateBitCast(StoredVal, StoredValTy);
}
// 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 (DL.isBigEndian()) {
uint64_t ShiftAmt = DL.getTypeStoreSizeInBits(StoredValTy) -
DL.getTypeStoreSizeInBits(LoadedTy);
StoredVal = IRB.CreateLShr(StoredVal, ShiftAmt, "tmp");
}
// Truncate the integer to the right size now.
Type *NewIntTy = IntegerType::get(StoredValTy->getContext(), LoadedValSize);
StoredVal = IRB.CreateTrunc(StoredVal, NewIntTy, "trunc");
if (LoadedTy != NewIntTy) {
// If the result is a pointer, inttoptr.
if (LoadedTy->getScalarType()->isPointerTy())
StoredVal = IRB.CreateIntToPtr(StoredVal, LoadedTy, "inttoptr");
else
// Otherwise, bitcast.
StoredVal = IRB.CreateBitCast(StoredVal, LoadedTy, "bitcast");
}
if (auto *C = dyn_cast<Constant>(StoredVal))
if (auto *FoldedStoredVal = ConstantFoldConstant(C, DL))
StoredVal = FoldedStoredVal;
return StoredVal;
}
/// This function is called when we have a
/// memdep query of a load that ends up being a clobbering memory write (store,
/// memset, memcpy, memmove). This means that the write *may* provide bits used
/// by the load but we can't be sure because the pointers don't mustalias.
///
/// Check this case to see if there is anything more we can do before we give
/// up. This returns -1 if we have to give up, or a byte number in the stored
/// value of the piece that feeds the load.
static int AnalyzeLoadFromClobberingWrite(Type *LoadTy, Value *LoadPtr,
Value *WritePtr,
uint64_t WriteSizeInBits,
const DataLayout &DL) {
// If the loaded or stored value is a first class array or struct, don't try
// to transform them. We need to be able to bitcast to integer.
if (LoadTy->isStructTy() || LoadTy->isArrayTy())
return -1;
int64_t StoreOffset = 0, LoadOffset = 0;
Value *StoreBase =
GetPointerBaseWithConstantOffset(WritePtr, StoreOffset, DL);
Value *LoadBase = GetPointerBaseWithConstantOffset(LoadPtr, LoadOffset, DL);
if (StoreBase != LoadBase)
return -1;
// If the load and store are to the exact same address, they should have been
// a must alias. AA must have gotten confused.
// FIXME: Study to see if/when this happens. One case is forwarding a memset
// to a load from the base of the memset.
// If the load and store don't overlap at all, the store doesn't provide
// anything to the load. In this case, they really don't alias at all, AA
// must have gotten confused.
uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy);
if ((WriteSizeInBits & 7) | (LoadSize & 7))
return -1;
uint64_t StoreSize = WriteSizeInBits / 8; // Convert to bytes.
LoadSize /= 8;
bool isAAFailure = false;
if (StoreOffset < LoadOffset)
isAAFailure = StoreOffset+int64_t(StoreSize) <= LoadOffset;
else
isAAFailure = LoadOffset+int64_t(LoadSize) <= StoreOffset;
if (isAAFailure)
return -1;
// If the Load isn't completely contained within the stored bits, we don't
// have all the bits to feed it. We could do something crazy in the future
// (issue a smaller load then merge the bits in) but this seems unlikely to be
// valuable.
if (StoreOffset > LoadOffset ||
StoreOffset+StoreSize < LoadOffset+LoadSize)
return -1;
// Okay, we can do this transformation. Return the number of bytes into the
// store that the load is.
return LoadOffset-StoreOffset;
}
/// This function is called when we have a
/// memdep query of a load that ends up being a clobbering store.
static int AnalyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr,
StoreInst *DepSI) {
// Cannot handle reading from store of first-class aggregate yet.
if (DepSI->getValueOperand()->getType()->isStructTy() ||
DepSI->getValueOperand()->getType()->isArrayTy())
return -1;
const DataLayout &DL = DepSI->getModule()->getDataLayout();
Value *StorePtr = DepSI->getPointerOperand();
uint64_t StoreSize =DL.getTypeSizeInBits(DepSI->getValueOperand()->getType());
return AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr,
StorePtr, StoreSize, DL);
}
/// This function is called when we have a
/// memdep query of a load that ends up being clobbered by another load. See if
/// the other load can feed into the second load.
static int AnalyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr,
LoadInst *DepLI, const DataLayout &DL){
// Cannot handle reading from store of first-class aggregate yet.
if (DepLI->getType()->isStructTy() || DepLI->getType()->isArrayTy())
return -1;
Value *DepPtr = DepLI->getPointerOperand();
uint64_t DepSize = DL.getTypeSizeInBits(DepLI->getType());
int R = AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr, DepPtr, DepSize, DL);
if (R != -1) return R;
// If we have a load/load clobber an DepLI can be widened to cover this load,
// then we should widen it!
int64_t LoadOffs = 0;
const Value *LoadBase =
GetPointerBaseWithConstantOffset(LoadPtr, LoadOffs, DL);
unsigned LoadSize = DL.getTypeStoreSize(LoadTy);
unsigned Size = MemoryDependenceResults::getLoadLoadClobberFullWidthSize(
LoadBase, LoadOffs, LoadSize, DepLI);
if (Size == 0) return -1;
// Check non-obvious conditions enforced by MDA which we rely on for being
// able to materialize this potentially available value
assert(DepLI->isSimple() && "Cannot widen volatile/atomic load!");
assert(DepLI->getType()->isIntegerTy() && "Can't widen non-integer load");
return AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr, DepPtr, Size*8, DL);
}
static int AnalyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr,
MemIntrinsic *MI,
const DataLayout &DL) {
// If the mem operation is a non-constant size, we can't handle it.
ConstantInt *SizeCst = dyn_cast<ConstantInt>(MI->getLength());
if (!SizeCst) return -1;
uint64_t MemSizeInBits = SizeCst->getZExtValue()*8;
// If this is memset, we just need to see if the offset is valid in the size
// of the memset..
if (MI->getIntrinsicID() == Intrinsic::memset)
return AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr, MI->getDest(),
MemSizeInBits, DL);
// If we have a memcpy/memmove, the only case we can handle is if this is a
// copy from constant memory. In that case, we can read directly from the
// constant memory.
MemTransferInst *MTI = cast<MemTransferInst>(MI);
Constant *Src = dyn_cast<Constant>(MTI->getSource());
if (!Src) return -1;
GlobalVariable *GV = dyn_cast<GlobalVariable>(GetUnderlyingObject(Src, DL));
if (!GV || !GV->isConstant()) return -1;
// See if the access is within the bounds of the transfer.
int Offset = AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr,
MI->getDest(), MemSizeInBits, DL);
if (Offset == -1)
return Offset;
unsigned AS = Src->getType()->getPointerAddressSpace();
// Otherwise, see if we can constant fold a load from the constant with the
// offset applied as appropriate.
Src = ConstantExpr::getBitCast(Src,
Type::getInt8PtrTy(Src->getContext(), AS));
Constant *OffsetCst =
ConstantInt::get(Type::getInt64Ty(Src->getContext()), (unsigned)Offset);
Src = ConstantExpr::getGetElementPtr(Type::getInt8Ty(Src->getContext()), Src,
OffsetCst);
Src = ConstantExpr::getBitCast(Src, PointerType::get(LoadTy, AS));
if (ConstantFoldLoadFromConstPtr(Src, LoadTy, DL))
return Offset;
return -1;
}
/// This function is called when we have a
/// memdep query of a load that ends up being a clobbering store. This means
/// that the store provides bits used by the load but we the pointers don't
/// mustalias. Check this case to see if there is anything more we can do
/// before we give up.
static Value *GetStoreValueForLoad(Value *SrcVal, unsigned Offset,
Type *LoadTy,
Instruction *InsertPt, const DataLayout &DL){
LLVMContext &Ctx = SrcVal->getType()->getContext();
uint64_t StoreSize = (DL.getTypeSizeInBits(SrcVal->getType()) + 7) / 8;
uint64_t LoadSize = (DL.getTypeSizeInBits(LoadTy) + 7) / 8;
IRBuilder<> Builder(InsertPt);
// Compute which bits of the stored value are being used by the load. Convert
// to an integer type to start with.
if (SrcVal->getType()->getScalarType()->isPointerTy())
SrcVal = Builder.CreatePtrToInt(SrcVal,
DL.getIntPtrType(SrcVal->getType()));
if (!SrcVal->getType()->isIntegerTy())
SrcVal = Builder.CreateBitCast(SrcVal, IntegerType::get(Ctx, StoreSize*8));
// Shift the bits to the least significant depending on endianness.
unsigned ShiftAmt;
if (DL.isLittleEndian())
ShiftAmt = Offset*8;
else
ShiftAmt = (StoreSize-LoadSize-Offset)*8;
if (ShiftAmt)
SrcVal = Builder.CreateLShr(SrcVal, ShiftAmt);
if (LoadSize != StoreSize)
SrcVal = Builder.CreateTrunc(SrcVal, IntegerType::get(Ctx, LoadSize*8));
return CoerceAvailableValueToLoadType(SrcVal, LoadTy, Builder, DL);
}
/// This function is called when we have a
/// memdep query of a load that ends up being a clobbering load. This means
/// that the load *may* provide bits used by the load but we can't be sure
/// because the pointers don't mustalias. Check this case to see if there is
/// anything more we can do before we give up.
static Value *GetLoadValueForLoad(LoadInst *SrcVal, unsigned Offset,
Type *LoadTy, Instruction *InsertPt,
GVN &gvn) {
const DataLayout &DL = SrcVal->getModule()->getDataLayout();
// If Offset+LoadTy exceeds the size of SrcVal, then we must be wanting to
// widen SrcVal out to a larger load.
unsigned SrcValStoreSize = DL.getTypeStoreSize(SrcVal->getType());
unsigned LoadSize = DL.getTypeStoreSize(LoadTy);
if (Offset+LoadSize > SrcValStoreSize) {
assert(SrcVal->isSimple() && "Cannot widen volatile/atomic load!");
assert(SrcVal->getType()->isIntegerTy() && "Can't widen non-integer load");
// If we have a load/load clobber an DepLI can be widened to cover this
// load, then we should widen it to the next power of 2 size big enough!
unsigned NewLoadSize = Offset+LoadSize;
if (!isPowerOf2_32(NewLoadSize))
NewLoadSize = NextPowerOf2(NewLoadSize);
Value *PtrVal = SrcVal->getPointerOperand();
// Insert the new load after the old load. This ensures that subsequent
// memdep queries will find the new load. We can't easily remove the old
// load completely because it is already in the value numbering table.
IRBuilder<> Builder(SrcVal->getParent(), ++BasicBlock::iterator(SrcVal));
Type *DestPTy =
IntegerType::get(LoadTy->getContext(), NewLoadSize*8);
DestPTy = PointerType::get(DestPTy,
PtrVal->getType()->getPointerAddressSpace());
Builder.SetCurrentDebugLocation(SrcVal->getDebugLoc());
PtrVal = Builder.CreateBitCast(PtrVal, DestPTy);
LoadInst *NewLoad = Builder.CreateLoad(PtrVal);
NewLoad->takeName(SrcVal);
NewLoad->setAlignment(SrcVal->getAlignment());
DEBUG(dbgs() << "GVN WIDENED LOAD: " << *SrcVal << "\n");
DEBUG(dbgs() << "TO: " << *NewLoad << "\n");
// Replace uses of the original load with the wider load. On a big endian
// system, we need to shift down to get the relevant bits.
Value *RV = NewLoad;
if (DL.isBigEndian())
RV = Builder.CreateLShr(RV, (NewLoadSize - SrcValStoreSize) * 8);
RV = Builder.CreateTrunc(RV, SrcVal->getType());
SrcVal->replaceAllUsesWith(RV);
// We would like to use gvn.markInstructionForDeletion here, but we can't
// because the load is already memoized into the leader map table that GVN
// tracks. It is potentially possible to remove the load from the table,
// but then there all of the operations based on it would need to be
// rehashed. Just leave the dead load around.
gvn.getMemDep().removeInstruction(SrcVal);
SrcVal = NewLoad;
}
return GetStoreValueForLoad(SrcVal, Offset, LoadTy, InsertPt, DL);
}
/// This function is called when we have a
/// memdep query of a load that ends up being a clobbering mem intrinsic.
static Value *GetMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset,
Type *LoadTy, Instruction *InsertPt,
const DataLayout &DL){
LLVMContext &Ctx = LoadTy->getContext();
uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy)/8;
IRBuilder<> Builder(InsertPt);
// We know that this method is only called when the mem transfer fully
// provides the bits for the load.
if (MemSetInst *MSI = dyn_cast<MemSetInst>(SrcInst)) {
// memset(P, 'x', 1234) -> splat('x'), even if x is a variable, and
// independently of what the offset is.
Value *Val = MSI->getValue();
if (LoadSize != 1)
Val = Builder.CreateZExt(Val, IntegerType::get(Ctx, LoadSize*8));
Value *OneElt = Val;
// Splat the value out to the right number of bits.
for (unsigned NumBytesSet = 1; NumBytesSet != LoadSize; ) {
// If we can double the number of bytes set, do it.
if (NumBytesSet*2 <= LoadSize) {
Value *ShVal = Builder.CreateShl(Val, NumBytesSet*8);
Val = Builder.CreateOr(Val, ShVal);
NumBytesSet <<= 1;
continue;
}
// Otherwise insert one byte at a time.
Value *ShVal = Builder.CreateShl(Val, 1*8);
Val = Builder.CreateOr(OneElt, ShVal);
++NumBytesSet;
}
return CoerceAvailableValueToLoadType(Val, LoadTy, Builder, DL);
}
// Otherwise, this is a memcpy/memmove from a constant global.
MemTransferInst *MTI = cast<MemTransferInst>(SrcInst);
Constant *Src = cast<Constant>(MTI->getSource());
unsigned AS = Src->getType()->getPointerAddressSpace();
// Otherwise, see if we can constant fold a load from the constant with the
// offset applied as appropriate.
Src = ConstantExpr::getBitCast(Src,
Type::getInt8PtrTy(Src->getContext(), AS));
Constant *OffsetCst =
ConstantInt::get(Type::getInt64Ty(Src->getContext()), (unsigned)Offset);
Src = ConstantExpr::getGetElementPtr(Type::getInt8Ty(Src->getContext()), Src,
OffsetCst);
Src = ConstantExpr::getBitCast(Src, PointerType::get(LoadTy, AS));
return ConstantFoldLoadFromConstPtr(Src, LoadTy, DL);
}
/// Given a set of loads specified by ValuesPerBlock, /// Given a set of loads specified by ValuesPerBlock,
/// construct SSA form, allowing us to eliminate LI. This returns the value /// construct SSA form, allowing us to eliminate LI. This returns the value
/// that should be used at LI's definition site. /// that should be used at LI's definition site.
static Value *ConstructSSAForLoadSet(LoadInst *LI, static Value *ConstructSSAForLoadSet(LoadInst *LI,
SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock, SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock,
GVN &gvn) { GVN &gvn) {
Show All 29 LinesValue *AvailableValue::MaterializeAdjustedValue(LoadInst *LI,
Instruction *InsertPt, Instruction *InsertPt,
GVN &gvn) const { GVN &gvn) const {
Value *Res; Value *Res;
Type *LoadTy = LI->getType(); Type *LoadTy = LI->getType();
const DataLayout &DL = LI->getModule()->getDataLayout(); const DataLayout &DL = LI->getModule()->getDataLayout();
if (isSimpleValue()) { if (isSimpleValue()) {
Res = getSimpleValue(); Res = getSimpleValue();
if (Res->getType() != LoadTy) { if (Res->getType() != LoadTy) {
Res = GetStoreValueForLoad(Res, Offset, LoadTy, InsertPt, DL); Res = getStoreValueForLoad(Res, Offset, LoadTy, InsertPt, DL);
DEBUG(dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offset << " " DEBUG(dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offset << " "
<< *getSimpleValue() << '\n' << *getSimpleValue() << '\n'
<< *Res << '\n' << "\n\n\n"); << *Res << '\n' << "\n\n\n");
} }
} else if (isCoercedLoadValue()) { } else if (isCoercedLoadValue()) {
LoadInst *Load = getCoercedLoadValue(); LoadInst *Load = getCoercedLoadValue();
if (Load->getType() == LoadTy && Offset == 0) { if (Load->getType() == LoadTy && Offset == 0) {
Res = Load; Res = Load;
} else { } else {
Res = GetLoadValueForLoad(Load, Offset, LoadTy, InsertPt, gvn); Res = getLoadValueForLoad(Load, Offset, LoadTy, InsertPt);
// We would like to use gvn.markInstructionForDeletion here, but we can't
// because the load is already memoized into the leader map table that GVN
// tracks. It is potentially possible to remove the load from the table,
// but then there all of the operations based on it would need to be
// rehashed. Just leave the dead load around.
gvn.getMemDep().removeInstruction(Load);
DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset << " " DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset << " "
<< *getCoercedLoadValue() << '\n' << *getCoercedLoadValue() << '\n'
<< *Res << '\n' << "\n\n\n"); << *Res << '\n'
<< "\n\n\n");
} }
} else if (isMemIntrinValue()) { } else if (isMemIntrinValue()) {
Res = GetMemInstValueForLoad(getMemIntrinValue(), Offset, LoadTy, Res = getMemInstValueForLoad(getMemIntrinValue(), Offset, LoadTy,
InsertPt, DL); InsertPt, DL);
DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset
<< " " << *getMemIntrinValue() << '\n' << " " << *getMemIntrinValue() << '\n'
<< *Res << '\n' << "\n\n\n"); << *Res << '\n' << "\n\n\n");
} else { } else {
assert(isUndefValue() && "Should be UndefVal"); assert(isUndefValue() && "Should be UndefVal");
DEBUG(dbgs() << "GVN COERCED NONLOCAL Undef:\n";); DEBUG(dbgs() << "GVN COERCED NONLOCAL Undef:\n";);
return UndefValue::get(LoadTy); return UndefValue::get(LoadTy);
▲ Show 20 Lines • Show All 52 Lines • ▼ Show 20 Linesbool GVN::AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
if (DepInfo.isClobber()) { if (DepInfo.isClobber()) {
// If the dependence is to a store that writes to a superset of the bits // If the dependence is to a store that writes to a superset of the bits
// read by the load, we can extract the bits we need for the load from the // read by the load, we can extract the bits we need for the load from the
// stored value. // stored value.
if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInfo.getInst())) { if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInfo.getInst())) {
// Can't forward from non-atomic to atomic without violating memory model. // Can't forward from non-atomic to atomic without violating memory model.
if (Address && LI->isAtomic() <= DepSI->isAtomic()) { if (Address && LI->isAtomic() <= DepSI->isAtomic()) {
int Offset = int Offset =
AnalyzeLoadFromClobberingStore(LI->getType(), Address, DepSI); analyzeLoadFromClobberingStore(LI->getType(), Address, DepSI);
if (Offset != -1) { if (Offset != -1) {
Res = AvailableValue::get(DepSI->getValueOperand(), Offset); Res = AvailableValue::get(DepSI->getValueOperand(), Offset);
return true; return true;
} }
} }
} }
// Check to see if we have something like this: // Check to see if we have something like this:
// load i32* P // load i32* P
// load i8* (P+1) // load i8* (P+1)
// if we have this, replace the later with an extraction from the former. // if we have this, replace the later with an extraction from the former.
if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInfo.getInst())) { if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInfo.getInst())) {
// If this is a clobber and L is the first instruction in its block, then // If this is a clobber and L is the first instruction in its block, then
// we have the first instruction in the entry block. // we have the first instruction in the entry block.
// Can't forward from non-atomic to atomic without violating memory model. // Can't forward from non-atomic to atomic without violating memory model.
if (DepLI != LI && Address && LI->isAtomic() <= DepLI->isAtomic()) { if (DepLI != LI && Address && LI->isAtomic() <= DepLI->isAtomic()) {
int Offset = int Offset =
AnalyzeLoadFromClobberingLoad(LI->getType(), Address, DepLI, DL); analyzeLoadFromClobberingLoad(LI->getType(), Address, DepLI, DL);
if (Offset != -1) { if (Offset != -1) {
Res = AvailableValue::getLoad(DepLI, Offset); Res = AvailableValue::getLoad(DepLI, Offset);
return true; return true;
} }
} }
} }
// If the clobbering value is a memset/memcpy/memmove, see if we can // If the clobbering value is a memset/memcpy/memmove, see if we can
// forward a value on from it. // forward a value on from it.
if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInfo.getInst())) { if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInfo.getInst())) {
if (Address && !LI->isAtomic()) { if (Address && !LI->isAtomic()) {
int Offset = AnalyzeLoadFromClobberingMemInst(LI->getType(), Address, int Offset = analyzeLoadFromClobberingMemInst(LI->getType(), Address,
DepMI, DL); DepMI, DL);
if (Offset != -1) { if (Offset != -1) {
Res = AvailableValue::getMI(DepMI, Offset); Res = AvailableValue::getMI(DepMI, Offset);
return true; return true;
} }
} }
} }
// Nothing known about this clobber, have to be conservative // Nothing known about this clobber, have to be conservative
Show All 28 Lines if (isCallocLikeFn(DepInst, TLI)) {
return true; return true;
} }
if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) { if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) {
// Reject loads and stores that are to the same address but are of // Reject loads and stores that are to the same address but are of
// different types if we have to. If the stored value is larger or equal to // different types if we have to. If the stored value is larger or equal to
// the loaded value, we can reuse it. // the loaded value, we can reuse it.
if (S->getValueOperand()->getType() != LI->getType() && if (S->getValueOperand()->getType() != LI->getType() &&
!CanCoerceMustAliasedValueToLoad(S->getValueOperand(), !canCoerceMustAliasedValueToLoad(S->getValueOperand(),
LI->getType(), DL)) LI->getType(), DL))
return false; return false;
// Can't forward from non-atomic to atomic without violating memory model. // Can't forward from non-atomic to atomic without violating memory model.
if (S->isAtomic() < LI->isAtomic()) if (S->isAtomic() < LI->isAtomic())
return false; return false;
Res = AvailableValue::get(S->getValueOperand()); Res = AvailableValue::get(S->getValueOperand());
return true; return true;
} }
if (LoadInst *LD = dyn_cast<LoadInst>(DepInst)) { if (LoadInst *LD = dyn_cast<LoadInst>(DepInst)) {
// If the types mismatch and we can't handle it, reject reuse of the load. // If the types mismatch and we can't handle it, reject reuse of the load.
// If the stored value is larger or equal to the loaded value, we can reuse // If the stored value is larger or equal to the loaded value, we can reuse
// it. // it.
if (LD->getType() != LI->getType() && if (LD->getType() != LI->getType() &&
!CanCoerceMustAliasedValueToLoad(LD, LI->getType(), DL)) !canCoerceMustAliasedValueToLoad(LD, LI->getType(), DL))
return false; return false;
// Can't forward from non-atomic to atomic without violating memory model. // Can't forward from non-atomic to atomic without violating memory model.
if (LD->isAtomic() < LI->isAtomic()) if (LD->isAtomic() < LI->isAtomic())
return false; return false;
Res = AvailableValue::getLoad(LD); Res = AvailableValue::getLoad(LD);
return true; return true;
▲ Show 20 Lines • Show All 1,448 Lines • Show Last 20 Lines

llvm/trunk/lib/Transforms/Utils/CMakeLists.txt

Show First 20 Lines • Show All 48 Lines • ▼ Show 20 Linesadd_llvm_library(LLVMTransformUtils
SimplifyInstructions.cpp SimplifyInstructions.cpp
SimplifyLibCalls.cpp SimplifyLibCalls.cpp
SplitModule.cpp SplitModule.cpp
StripNonLineTableDebugInfo.cpp StripNonLineTableDebugInfo.cpp
SymbolRewriter.cpp SymbolRewriter.cpp
UnifyFunctionExitNodes.cpp UnifyFunctionExitNodes.cpp
Utils.cpp Utils.cpp
ValueMapper.cpp ValueMapper.cpp
VNCoercion.cpp
ADDITIONAL_HEADER_DIRS ADDITIONAL_HEADER_DIRS
${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms/Utils ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms/Utils
DEPENDS DEPENDS
intrinsics_gen intrinsics_gen
) )

llvm/trunk/lib/Transforms/Utils/VNCoercion.cpp

#include "llvm/Transforms/Utils/VNCoercion.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Support/Debug.h"
#define DEBUG_TYPE "vncoerce"
namespace llvm {
namespace VNCoercion {
/// Return true if coerceAvailableValueToLoadType will succeed.
bool canCoerceMustAliasedValueToLoad(Value *StoredVal, Type *LoadTy,
const DataLayout &DL) {
// If the loaded or stored value is an first class array or struct, don't try
// to transform them. We need to be able to bitcast to integer.
if (LoadTy->isStructTy() || LoadTy->isArrayTy() ||
StoredVal->getType()->isStructTy() || StoredVal->getType()->isArrayTy())
return false;
// The store has to be at least as big as the load.
if (DL.getTypeSizeInBits(StoredVal->getType()) < DL.getTypeSizeInBits(LoadTy))
return false;
return true;
}
/// 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. LoadedTy is the type of the load we want to replace.
/// IRB is IRBuilder used to insert new instructions.
///
/// If we can't do it, return null.
Value *coerceAvailableValueToLoadType(Value *StoredVal, Type *LoadedTy,
IRBuilder<> &IRB, const DataLayout &DL) {
assert(canCoerceMustAliasedValueToLoad(StoredVal, LoadedTy, DL) &&
"precondition violation - materialization can't fail");
if (auto *C = dyn_cast<Constant>(StoredVal))
if (auto *FoldedStoredVal = ConstantFoldConstant(C, DL))
StoredVal = FoldedStoredVal;
// If this is already the right type, just return it.
Type *StoredValTy = StoredVal->getType();
uint64_t StoredValSize = DL.getTypeSizeInBits(StoredValTy);
uint64_t LoadedValSize = DL.getTypeSizeInBits(LoadedTy);
// If the store and reload are the same size, we can always reuse it.
if (StoredValSize == LoadedValSize) {
// Pointer to Pointer -> use bitcast.
if (StoredValTy->getScalarType()->isPointerTy() &&
LoadedTy->getScalarType()->isPointerTy()) {
StoredVal = IRB.CreateBitCast(StoredVal, LoadedTy);
} else {
// Convert source pointers to integers, which can be bitcast.
if (StoredValTy->getScalarType()->isPointerTy()) {
StoredValTy = DL.getIntPtrType(StoredValTy);
StoredVal = IRB.CreatePtrToInt(StoredVal, StoredValTy);
}
Type *TypeToCastTo = LoadedTy;
if (TypeToCastTo->getScalarType()->isPointerTy())
TypeToCastTo = DL.getIntPtrType(TypeToCastTo);
if (StoredValTy != TypeToCastTo)
StoredVal = IRB.CreateBitCast(StoredVal, TypeToCastTo);
// Cast to pointer if the load needs a pointer type.
if (LoadedTy->getScalarType()->isPointerTy())
StoredVal = IRB.CreateIntToPtr(StoredVal, LoadedTy);
}
if (auto *C = dyn_cast<ConstantExpr>(StoredVal))
if (auto *FoldedStoredVal = ConstantFoldConstant(C, DL))
StoredVal = FoldedStoredVal;
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.
assert(StoredValSize >= LoadedValSize &&
"canCoerceMustAliasedValueToLoad fail");
// Convert source pointers to integers, which can be manipulated.
if (StoredValTy->getScalarType()->isPointerTy()) {
StoredValTy = DL.getIntPtrType(StoredValTy);
StoredVal = IRB.CreatePtrToInt(StoredVal, StoredValTy);
}
// Convert vectors and fp to integer, which can be manipulated.
if (!StoredValTy->isIntegerTy()) {
StoredValTy = IntegerType::get(StoredValTy->getContext(), StoredValSize);
StoredVal = IRB.CreateBitCast(StoredVal, StoredValTy);
}
// 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 (DL.isBigEndian()) {
uint64_t ShiftAmt = DL.getTypeStoreSizeInBits(StoredValTy) -
DL.getTypeStoreSizeInBits(LoadedTy);
StoredVal = IRB.CreateLShr(StoredVal, ShiftAmt, "tmp");
}
// Truncate the integer to the right size now.
Type *NewIntTy = IntegerType::get(StoredValTy->getContext(), LoadedValSize);
StoredVal = IRB.CreateTrunc(StoredVal, NewIntTy, "trunc");
if (LoadedTy != NewIntTy) {
// If the result is a pointer, inttoptr.
if (LoadedTy->getScalarType()->isPointerTy())
StoredVal = IRB.CreateIntToPtr(StoredVal, LoadedTy, "inttoptr");
else
// Otherwise, bitcast.
StoredVal = IRB.CreateBitCast(StoredVal, LoadedTy, "bitcast");
}
if (auto *C = dyn_cast<Constant>(StoredVal))
if (auto *FoldedStoredVal = ConstantFoldConstant(C, DL))
StoredVal = FoldedStoredVal;
return StoredVal;
}
/// This function is called when we have a
/// memdep query of a load that ends up being a clobbering memory write (store,
/// memset, memcpy, memmove). This means that the write *may* provide bits used
/// by the load but we can't be sure because the pointers don't mustalias.
///
/// Check this case to see if there is anything more we can do before we give
/// up. This returns -1 if we have to give up, or a byte number in the stored
/// value of the piece that feeds the load.
static int analyzeLoadFromClobberingWrite(Type *LoadTy, Value *LoadPtr,
Value *WritePtr,
uint64_t WriteSizeInBits,
const DataLayout &DL) {
// If the loaded or stored value is a first class array or struct, don't try
// to transform them. We need to be able to bitcast to integer.
if (LoadTy->isStructTy() || LoadTy->isArrayTy())
return -1;
int64_t StoreOffset = 0, LoadOffset = 0;
Value *StoreBase =
GetPointerBaseWithConstantOffset(WritePtr, StoreOffset, DL);
Value *LoadBase = GetPointerBaseWithConstantOffset(LoadPtr, LoadOffset, DL);
if (StoreBase != LoadBase)
return -1;
// If the load and store are to the exact same address, they should have been
// a must alias. AA must have gotten confused.
// FIXME: Study to see if/when this happens. One case is forwarding a memset
// to a load from the base of the memset.
// If the load and store don't overlap at all, the store doesn't provide
// anything to the load. In this case, they really don't alias at all, AA
// must have gotten confused.
uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy);
if ((WriteSizeInBits & 7) | (LoadSize & 7))
return -1;
uint64_t StoreSize = WriteSizeInBits / 8; // Convert to bytes.
LoadSize /= 8;
bool isAAFailure = false;
if (StoreOffset < LoadOffset)
isAAFailure = StoreOffset + int64_t(StoreSize) <= LoadOffset;
else
isAAFailure = LoadOffset + int64_t(LoadSize) <= StoreOffset;
if (isAAFailure)
return -1;
// If the Load isn't completely contained within the stored bits, we don't
// have all the bits to feed it. We could do something crazy in the future
// (issue a smaller load then merge the bits in) but this seems unlikely to be
// valuable.
if (StoreOffset > LoadOffset ||
StoreOffset + StoreSize < LoadOffset + LoadSize)
return -1;
// Okay, we can do this transformation. Return the number of bytes into the
// store that the load is.
return LoadOffset - StoreOffset;
}
/// This function is called when we have a
/// memdep query of a load that ends up being a clobbering store.
int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr,
StoreInst *DepSI) {
// Cannot handle reading from store of first-class aggregate yet.
if (DepSI->getValueOperand()->getType()->isStructTy() ||
DepSI->getValueOperand()->getType()->isArrayTy())
return -1;
const DataLayout &DL = DepSI->getModule()->getDataLayout();
Value *StorePtr = DepSI->getPointerOperand();
uint64_t StoreSize =
DL.getTypeSizeInBits(DepSI->getValueOperand()->getType());
return analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, StorePtr, StoreSize,
DL);
}
/// This function is called when we have a
/// memdep query of a load that ends up being clobbered by another load. See if
/// the other load can feed into the second load.
int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI,
const DataLayout &DL) {
// Cannot handle reading from store of first-class aggregate yet.
if (DepLI->getType()->isStructTy() || DepLI->getType()->isArrayTy())
return -1;
Value *DepPtr = DepLI->getPointerOperand();
uint64_t DepSize = DL.getTypeSizeInBits(DepLI->getType());
int R = analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, DepPtr, DepSize, DL);
if (R != -1)
return R;
// If we have a load/load clobber an DepLI can be widened to cover this load,
// then we should widen it!
int64_t LoadOffs = 0;
const Value *LoadBase =
GetPointerBaseWithConstantOffset(LoadPtr, LoadOffs, DL);
unsigned LoadSize = DL.getTypeStoreSize(LoadTy);
unsigned Size = MemoryDependenceResults::getLoadLoadClobberFullWidthSize(
LoadBase, LoadOffs, LoadSize, DepLI);
if (Size == 0)
return -1;
// Check non-obvious conditions enforced by MDA which we rely on for being
// able to materialize this potentially available value
assert(DepLI->isSimple() && "Cannot widen volatile/atomic load!");
assert(DepLI->getType()->isIntegerTy() && "Can't widen non-integer load");
return analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, DepPtr, Size * 8, DL);
}
int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr,
MemIntrinsic *MI, const DataLayout &DL) {
// If the mem operation is a non-constant size, we can't handle it.
ConstantInt *SizeCst = dyn_cast<ConstantInt>(MI->getLength());
if (!SizeCst)
return -1;
uint64_t MemSizeInBits = SizeCst->getZExtValue() * 8;
// If this is memset, we just need to see if the offset is valid in the size
// of the memset..
if (MI->getIntrinsicID() == Intrinsic::memset)
return analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, MI->getDest(),
MemSizeInBits, DL);
// If we have a memcpy/memmove, the only case we can handle is if this is a
// copy from constant memory. In that case, we can read directly from the
// constant memory.
MemTransferInst *MTI = cast<MemTransferInst>(MI);
Constant *Src = dyn_cast<Constant>(MTI->getSource());
if (!Src)
return -1;
GlobalVariable *GV = dyn_cast<GlobalVariable>(GetUnderlyingObject(Src, DL));
if (!GV || !GV->isConstant())
return -1;
// See if the access is within the bounds of the transfer.
int Offset = analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, MI->getDest(),
MemSizeInBits, DL);
if (Offset == -1)
return Offset;
unsigned AS = Src->getType()->getPointerAddressSpace();
// Otherwise, see if we can constant fold a load from the constant with the
// offset applied as appropriate.
Src =
ConstantExpr::getBitCast(Src, Type::getInt8PtrTy(Src->getContext(), AS));
Constant *OffsetCst =
ConstantInt::get(Type::getInt64Ty(Src->getContext()), (unsigned)Offset);
Src = ConstantExpr::getGetElementPtr(Type::getInt8Ty(Src->getContext()), Src,
OffsetCst);
Src = ConstantExpr::getBitCast(Src, PointerType::get(LoadTy, AS));
if (ConstantFoldLoadFromConstPtr(Src, LoadTy, DL))
return Offset;
return -1;
}
/// This function is called when we have a
/// memdep query of a load that ends up being a clobbering store. This means
/// that the store provides bits used by the load but we the pointers don't
/// mustalias. Check this case to see if there is anything more we can do
/// before we give up.
Value *getStoreValueForLoad(Value *SrcVal, unsigned Offset, Type *LoadTy,
Instruction *InsertPt, const DataLayout &DL) {
LLVMContext &Ctx = SrcVal->getType()->getContext();
uint64_t StoreSize = (DL.getTypeSizeInBits(SrcVal->getType()) + 7) / 8;
uint64_t LoadSize = (DL.getTypeSizeInBits(LoadTy) + 7) / 8;
IRBuilder<> Builder(InsertPt);
// Compute which bits of the stored value are being used by the load. Convert
// to an integer type to start with.
if (SrcVal->getType()->getScalarType()->isPointerTy())
SrcVal =
Builder.CreatePtrToInt(SrcVal, DL.getIntPtrType(SrcVal->getType()));
if (!SrcVal->getType()->isIntegerTy())
SrcVal =
Builder.CreateBitCast(SrcVal, IntegerType::get(Ctx, StoreSize * 8));
// Shift the bits to the least significant depending on endianness.
unsigned ShiftAmt;
if (DL.isLittleEndian())
ShiftAmt = Offset * 8;
else
ShiftAmt = (StoreSize - LoadSize - Offset) * 8;
if (ShiftAmt)
SrcVal = Builder.CreateLShr(SrcVal, ShiftAmt);
if (LoadSize != StoreSize)
SrcVal = Builder.CreateTrunc(SrcVal, IntegerType::get(Ctx, LoadSize * 8));
return coerceAvailableValueToLoadType(SrcVal, LoadTy, Builder, DL);
}
/// This function is called when we have a
/// memdep query of a load that ends up being a clobbering load. This means
/// that the load *may* provide bits used by the load but we can't be sure
/// because the pointers don't mustalias. Check this case to see if there is
/// anything more we can do before we give up.
Value *getLoadValueForLoad(LoadInst *SrcVal, unsigned Offset, Type *LoadTy,
Instruction *InsertPt) {
const DataLayout &DL = SrcVal->getModule()->getDataLayout();
// If Offset+LoadTy exceeds the size of SrcVal, then we must be wanting to
// widen SrcVal out to a larger load.
unsigned SrcValStoreSize = DL.getTypeStoreSize(SrcVal->getType());
unsigned LoadSize = DL.getTypeStoreSize(LoadTy);
if (Offset + LoadSize > SrcValStoreSize) {
assert(SrcVal->isSimple() && "Cannot widen volatile/atomic load!");
assert(SrcVal->getType()->isIntegerTy() && "Can't widen non-integer load");
// If we have a load/load clobber an DepLI can be widened to cover this
// load, then we should widen it to the next power of 2 size big enough!
unsigned NewLoadSize = Offset + LoadSize;
if (!isPowerOf2_32(NewLoadSize))
NewLoadSize = NextPowerOf2(NewLoadSize);
Value *PtrVal = SrcVal->getPointerOperand();
// Insert the new load after the old load. This ensures that subsequent
// memdep queries will find the new load. We can't easily remove the old
// load completely because it is already in the value numbering table.
IRBuilder<> Builder(SrcVal->getParent(), ++BasicBlock::iterator(SrcVal));
Type *DestPTy = IntegerType::get(LoadTy->getContext(), NewLoadSize * 8);
DestPTy =
PointerType::get(DestPTy, PtrVal->getType()->getPointerAddressSpace());
Builder.SetCurrentDebugLocation(SrcVal->getDebugLoc());
PtrVal = Builder.CreateBitCast(PtrVal, DestPTy);
LoadInst *NewLoad = Builder.CreateLoad(PtrVal);
NewLoad->takeName(SrcVal);
NewLoad->setAlignment(SrcVal->getAlignment());
DEBUG(dbgs() << "GVN WIDENED LOAD: " << *SrcVal << "\n");
DEBUG(dbgs() << "TO: " << *NewLoad << "\n");
// Replace uses of the original load with the wider load. On a big endian
// system, we need to shift down to get the relevant bits.
Value *RV = NewLoad;
if (DL.isBigEndian())
RV = Builder.CreateLShr(RV, (NewLoadSize - SrcValStoreSize) * 8);
RV = Builder.CreateTrunc(RV, SrcVal->getType());
SrcVal->replaceAllUsesWith(RV);
SrcVal = NewLoad;
}
return getStoreValueForLoad(SrcVal, Offset, LoadTy, InsertPt, DL);
}
/// This function is called when we have a
/// memdep query of a load that ends up being a clobbering mem intrinsic.
Value *getMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset,
Type *LoadTy, Instruction *InsertPt,
const DataLayout &DL) {
LLVMContext &Ctx = LoadTy->getContext();
uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy) / 8;
IRBuilder<> Builder(InsertPt);
// We know that this method is only called when the mem transfer fully
// provides the bits for the load.
if (MemSetInst *MSI = dyn_cast<MemSetInst>(SrcInst)) {
// memset(P, 'x', 1234) -> splat('x'), even if x is a variable, and
// independently of what the offset is.
Value *Val = MSI->getValue();
if (LoadSize != 1)
Val = Builder.CreateZExt(Val, IntegerType::get(Ctx, LoadSize * 8));
Value *OneElt = Val;
// Splat the value out to the right number of bits.
for (unsigned NumBytesSet = 1; NumBytesSet != LoadSize;) {
// If we can double the number of bytes set, do it.
if (NumBytesSet * 2 <= LoadSize) {
Value *ShVal = Builder.CreateShl(Val, NumBytesSet * 8);
Val = Builder.CreateOr(Val, ShVal);
NumBytesSet <<= 1;
continue;
}
// Otherwise insert one byte at a time.
Value *ShVal = Builder.CreateShl(Val, 1 * 8);
Val = Builder.CreateOr(OneElt, ShVal);
++NumBytesSet;
}
return coerceAvailableValueToLoadType(Val, LoadTy, Builder, DL);
}
// Otherwise, this is a memcpy/memmove from a constant global.
MemTransferInst *MTI = cast<MemTransferInst>(SrcInst);
Constant *Src = cast<Constant>(MTI->getSource());
unsigned AS = Src->getType()->getPointerAddressSpace();
// Otherwise, see if we can constant fold a load from the constant with the
// offset applied as appropriate.
Src =
ConstantExpr::getBitCast(Src, Type::getInt8PtrTy(Src->getContext(), AS));
Constant *OffsetCst =
ConstantInt::get(Type::getInt64Ty(Src->getContext()), (unsigned)Offset);
Src = ConstantExpr::getGetElementPtr(Type::getInt8Ty(Src->getContext()), Src,
OffsetCst);
Src = ConstantExpr::getBitCast(Src, PointerType::get(LoadTy, AS));
return ConstantFoldLoadFromConstPtr(Src, LoadTy, DL);
}
} // namespace VNCoercion
} // namespace llvm