/// Mapping from live pointers to a base-defining-value
DenseMap<llvm::Value *, llvm::Value *> PointerToBase;
- /// Any new values which were added to the IR during base pointer analysis
- /// for this safepoint
- DenseSet<llvm::Value *> NewInsertedDefs;
-
/// The *new* gc.statepoint instruction itself. This produces the token
/// that normal path gc.relocates and the gc.result are tied to.
Instruction *StatepointToken;
result.liveset = liveset;
}
-/// If we can trivially determine that this vector contains only base pointers,
-/// return the base instruction.
-static Value *findBaseOfVector(Value *I) {
+static Value *findBaseDefiningValue(Value *I);
+
+/// If we can trivially determine that the index specified in the given vector
+/// is a base pointer, return it. In cases where the entire vector is known to
+/// consist of base pointers, the entire vector will be returned. This
+/// indicates that the relevant extractelement is a valid base pointer and
+/// should be used directly.
+static Value *findBaseOfVector(Value *I, Value *Index) {
assert(I->getType()->isVectorTy() &&
cast<VectorType>(I->getType())->getElementType()->isPointerTy() &&
"Illegal to ask for the base pointer of a non-pointer type");
if (isa<LoadInst>(I))
return I;
+ // For an insert element, we might be able to look through it if we know
+ // something about the indexes, but if the indices are arbitrary values, we
+ // can't without much more extensive scalarization.
+ if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(I)) {
+ Value *InsertIndex = IEI->getOperand(2);
+ // This index is inserting the value, look for it's base
+ if (InsertIndex == Index)
+ return findBaseDefiningValue(IEI->getOperand(1));
+ // Both constant, and can't be equal per above. This insert is definitely
+ // not relevant, look back at the rest of the vector and keep trying.
+ if (isa<ConstantInt>(Index) && isa<ConstantInt>(InsertIndex))
+ return findBaseOfVector(IEI->getOperand(0), Index);
+ }
+
// Note: This code is currently rather incomplete. We are essentially only
// handling cases where the vector element is trivially a base pointer. We
// need to update the entire base pointer construction algorithm to know how
"Illegal to ask for the base pointer of a non-pointer type");
// This case is a bit of a hack - it only handles extracts from vectors which
- // trivially contain only base pointers. See note inside the function for
- // how to improve this.
+ // trivially contain only base pointers or cases where we can directly match
+ // the index of the original extract element to an insertion into the vector.
+ // See note inside the function for how to improve this.
if (auto *EEI = dyn_cast<ExtractElementInst>(I)) {
Value *VectorOperand = EEI->getVectorOperand();
- Value *VectorBase = findBaseOfVector(VectorOperand);
- (void)VectorBase;
- assert(VectorBase && "extract element not known to be a trivial base");
- return EEI;
+ Value *Index = EEI->getIndexOperand();
+ Value *VectorBase = findBaseOfVector(VectorOperand, Index);
+ // If the result returned is a vector, we know the entire vector must
+ // contain base pointers. In that case, the extractelement is a valid base
+ // for this value.
+ if (VectorBase->getType()->isVectorTy())
+ return EEI;
+ // Otherwise, we needed to look through the vector to find the base for
+ // this particular element.
+ assert(VectorBase->getType()->isPointerTy());
+ return VectorBase;
}
if (isa<Argument>(I))
/// from. For gc objects, this is simply itself. On success, returns a value
/// which is the base pointer. (This is reliable and can be used for
/// relocation.) On failure, returns nullptr.
-static Value *findBasePointer(Value *I, DefiningValueMapTy &cache,
- DenseSet<llvm::Value *> &NewInsertedDefs) {
+static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) {
Value *def = findBaseOrBDV(I, cache);
if (isKnownBaseResult(def)) {
std::distance(pred_begin(v->getParent()), pred_end(v->getParent()));
assert(num_preds > 0 && "how did we reach here");
PHINode *phi = PHINode::Create(v->getType(), num_preds, "base_phi", v);
- NewInsertedDefs.insert(phi);
// Add metadata marking this as a base value
auto *const_1 = ConstantInt::get(
Type::getInt32Ty(
UndefValue *undef = UndefValue::get(sel->getType());
SelectInst *basesel = SelectInst::Create(sel->getCondition(), undef,
undef, "base_select", sel);
- NewInsertedDefs.insert(basesel);
// Add metadata marking this as a base value
auto *const_1 = ConstantInt::get(
Type::getInt32Ty(
assert(states.count(base));
base = states[base].getBase();
assert(base != nullptr && "unknown PhiState!");
- assert(NewInsertedDefs.count(base) &&
- "should have already added this in a prev. iteration!");
}
// In essense this assert states: the only way two
if (base->getType() != basephi->getType()) {
base = new BitCastInst(base, basephi->getType(), "cast",
InBB->getTerminator());
- NewInsertedDefs.insert(base);
}
basephi->addIncoming(base, InBB);
}
// The cast is needed since base traversal may strip away bitcasts
if (base->getType() != basesel->getType()) {
base = new BitCastInst(base, basesel->getType(), "cast", basesel);
- NewInsertedDefs.insert(base);
}
basesel->setOperand(i, base);
}
static void
findBasePointers(const StatepointLiveSetTy &live,
DenseMap<llvm::Value *, llvm::Value *> &PointerToBase,
- DominatorTree *DT, DefiningValueMapTy &DVCache,
- DenseSet<llvm::Value *> &NewInsertedDefs) {
+ DominatorTree *DT, DefiningValueMapTy &DVCache) {
// For the naming of values inserted to be deterministic - which makes for
// much cleaner and more stable tests - we need to assign an order to the
// live values. DenseSets do not provide a deterministic order across runs.
Temp.insert(Temp.end(), live.begin(), live.end());
std::sort(Temp.begin(), Temp.end(), order_by_name);
for (Value *ptr : Temp) {
- Value *base = findBasePointer(ptr, DVCache, NewInsertedDefs);
+ Value *base = findBasePointer(ptr, DVCache);
assert(base && "failed to find base pointer");
PointerToBase[ptr] = base;
assert((!isa<Instruction>(base) || !isa<Instruction>(ptr) ||
const CallSite &CS,
PartiallyConstructedSafepointRecord &result) {
DenseMap<llvm::Value *, llvm::Value *> PointerToBase;
- DenseSet<llvm::Value *> NewInsertedDefs;
- findBasePointers(result.liveset, PointerToBase, &DT, DVCache,
- NewInsertedDefs);
+ findBasePointers(result.liveset, PointerToBase, &DT, DVCache);
if (PrintBasePointers) {
// Note: Need to print these in a stable order since this is checked in
}
result.PointerToBase = PointerToBase;
- result.NewInsertedDefs = NewInsertedDefs;
}
/// Given an updated version of the dataflow liveness results, update the
}
}
-// Normalize basic block to make it ready to be target of invoke statepoint.
-// It means spliting it to have single predecessor. Return newly created BB
-// ready to be successor of invoke statepoint.
-static BasicBlock *normalizeBBForInvokeSafepoint(BasicBlock *BB,
- BasicBlock *InvokeParent,
- Pass *P) {
- BasicBlock *ret = BB;
-
+// When inserting gc.relocate calls, we need to ensure there are no uses
+// of the original value between the gc.statepoint and the gc.relocate call.
+// One case which can arise is a phi node starting one of the successor blocks.
+// We also need to be able to insert the gc.relocates only on the path which
+// goes through the statepoint. We might need to split an edge to make this
+// possible.
+static BasicBlock *
+normalizeForInvokeSafepoint(BasicBlock *BB, BasicBlock *InvokeParent, Pass *P) {
+ DominatorTree *DT = nullptr;
+ if (auto *DTP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>())
+ DT = &DTP->getDomTree();
+
+ BasicBlock *Ret = BB;
if (!BB->getUniquePredecessor()) {
- ret = SplitBlockPredecessors(BB, InvokeParent, "");
+ Ret = SplitBlockPredecessors(BB, InvokeParent, "", nullptr, DT);
}
- // Another requirement for such basic blocks is to not have any phi nodes.
- // Since we just ensured that new BB will have single predecessor,
- // all phi nodes in it will have one value. Here it would be naturall place
- // to
- // remove them all. But we can not do this because we are risking to remove
- // one of the values stored in liveset of another statepoint. We will do it
- // later after placing all safepoints.
+ // Now that 'ret' has unique predecessor we can safely remove all phi nodes
+ // from it
+ FoldSingleEntryPHINodes(Ret);
+ assert(!isa<PHINode>(Ret->begin()));
- return ret;
+ // At this point, we can safely insert a gc.relocate as the first instruction
+ // in Ret if needed.
+ return Ret;
}
static int find_index(ArrayRef<Value *> livevec, Value *val) {
/// statepointToken - statepoint instruction to which relocates should be
/// bound.
/// Builder - Llvm IR builder to be used to construct new calls.
-static void CreateGCRelocates(ArrayRef<llvm::Value *> liveVariables,
- const int liveStart,
- ArrayRef<llvm::Value *> basePtrs,
- Instruction *statepointToken,
+static void CreateGCRelocates(ArrayRef<llvm::Value *> LiveVariables,
+ const int LiveStart,
+ ArrayRef<llvm::Value *> BasePtrs,
+ Instruction *StatepointToken,
IRBuilder<> Builder) {
SmallVector<Instruction *, 64> NewDefs;
- NewDefs.reserve(liveVariables.size());
+ NewDefs.reserve(LiveVariables.size());
- Module *M = statepointToken->getParent()->getParent()->getParent();
+ Module *M = StatepointToken->getParent()->getParent()->getParent();
- for (unsigned i = 0; i < liveVariables.size(); i++) {
+ for (unsigned i = 0; i < LiveVariables.size(); i++) {
// We generate a (potentially) unique declaration for every pointer type
// combination. This results is some blow up the function declarations in
// the IR, but removes the need for argument bitcasts which shrinks the IR
// greatly and makes it much more readable.
- SmallVector<Type *, 1> types; // one per 'any' type
- types.push_back(liveVariables[i]->getType()); // result type
- Value *gc_relocate_decl = Intrinsic::getDeclaration(
- M, Intrinsic::experimental_gc_relocate, types);
+ SmallVector<Type *, 1> Types; // one per 'any' type
+ // All gc_relocate are set to i8 addrspace(1)* type. This could help avoid
+ // cases where the actual value's type mangling is not supported by llvm. A
+ // bitcast is added later to convert gc_relocate to the actual value's type.
+ Types.push_back(Type::getInt8PtrTy(M->getContext(), 1));
+ Value *GCRelocateDecl = Intrinsic::getDeclaration(
+ M, Intrinsic::experimental_gc_relocate, Types);
// Generate the gc.relocate call and save the result
- Value *baseIdx =
+ Value *BaseIdx =
ConstantInt::get(Type::getInt32Ty(M->getContext()),
- liveStart + find_index(liveVariables, basePtrs[i]));
- Value *liveIdx = ConstantInt::get(
+ LiveStart + find_index(LiveVariables, BasePtrs[i]));
+ Value *LiveIdx = ConstantInt::get(
Type::getInt32Ty(M->getContext()),
- liveStart + find_index(liveVariables, liveVariables[i]));
+ LiveStart + find_index(LiveVariables, LiveVariables[i]));
// only specify a debug name if we can give a useful one
- Value *reloc = Builder.CreateCall3(
- gc_relocate_decl, statepointToken, baseIdx, liveIdx,
- liveVariables[i]->hasName() ? liveVariables[i]->getName() + ".relocated"
+ Value *Reloc = Builder.CreateCall3(
+ GCRelocateDecl, StatepointToken, BaseIdx, LiveIdx,
+ LiveVariables[i]->hasName() ? LiveVariables[i]->getName() + ".relocated"
: "");
// Trick CodeGen into thinking there are lots of free registers at this
// fake call.
- cast<CallInst>(reloc)->setCallingConv(CallingConv::Cold);
+ cast<CallInst>(Reloc)->setCallingConv(CallingConv::Cold);
- NewDefs.push_back(cast<Instruction>(reloc));
+ NewDefs.push_back(cast<Instruction>(Reloc));
}
- assert(NewDefs.size() == liveVariables.size() &&
+ assert(NewDefs.size() == LiveVariables.size() &&
"missing or extra redefinition at safepoint");
}
token = invoke;
// Generate gc relocates in exceptional path
- BasicBlock *unwindBlock = normalizeBBForInvokeSafepoint(
- toReplace->getUnwindDest(), invoke->getParent(), P);
+ BasicBlock *unwindBlock = toReplace->getUnwindDest();
+ assert(!isa<PHINode>(unwindBlock->begin()) &&
+ unwindBlock->getUniquePredecessor() &&
+ "can't safely insert in this block!");
Instruction *IP = &*(unwindBlock->getFirstInsertionPt());
Builder.SetInsertPoint(IP);
exceptional_token, Builder);
// Generate gc relocates and returns for normal block
- BasicBlock *normalDest = normalizeBBForInvokeSafepoint(
- toReplace->getNormalDest(), invoke->getParent(), P);
+ BasicBlock *normalDest = toReplace->getNormalDest();
+ assert(!isa<PHINode>(normalDest->begin()) &&
+ normalDest->getUniquePredecessor() &&
+ "can't safely insert in this block!");
IP = &*(normalDest->getFirstInsertionPt());
Builder.SetInsertPoint(IP);
// Add visited values into the visitedLiveValues set we will later use them
// for sanity check.
static void
-insertRelocationStores(iterator_range<Value::user_iterator> gcRelocs,
- DenseMap<Value *, Value *> &allocaMap,
- DenseSet<Value *> &visitedLiveValues) {
+insertRelocationStores(iterator_range<Value::user_iterator> GCRelocs,
+ DenseMap<Value *, Value *> &AllocaMap,
+ DenseSet<Value *> &VisitedLiveValues) {
- for (User *U : gcRelocs) {
+ for (User *U : GCRelocs) {
if (!isa<IntrinsicInst>(U))
continue;
- IntrinsicInst *relocatedValue = cast<IntrinsicInst>(U);
+ IntrinsicInst *RelocatedValue = cast<IntrinsicInst>(U);
// We only care about relocates
- if (relocatedValue->getIntrinsicID() !=
+ if (RelocatedValue->getIntrinsicID() !=
Intrinsic::experimental_gc_relocate) {
continue;
}
- GCRelocateOperands relocateOperands(relocatedValue);
- Value *originalValue = const_cast<Value *>(relocateOperands.derivedPtr());
- assert(allocaMap.count(originalValue));
- Value *alloca = allocaMap[originalValue];
+ GCRelocateOperands RelocateOperands(RelocatedValue);
+ Value *OriginalValue =
+ const_cast<Value *>(RelocateOperands.getDerivedPtr());
+ assert(AllocaMap.count(OriginalValue));
+ Value *Alloca = AllocaMap[OriginalValue];
// Emit store into the related alloca
- StoreInst *store = new StoreInst(relocatedValue, alloca);
- store->insertAfter(relocatedValue);
+ // All gc_relocate are i8 addrspace(1)* typed, and it must be bitcasted to
+ // the correct type according to alloca.
+ assert(RelocatedValue->getNextNode() && "Should always have one since it's not a terminator");
+ IRBuilder<> Builder(RelocatedValue->getNextNode());
+ Value *CastedRelocatedValue =
+ Builder.CreateBitCast(RelocatedValue, cast<AllocaInst>(Alloca)->getAllocatedType(),
+ RelocatedValue->hasName() ? RelocatedValue->getName() + ".casted" : "");
+
+ StoreInst *Store = new StoreInst(CastedRelocatedValue, Alloca);
+ Store->insertAfter(cast<Instruction>(CastedRelocatedValue));
#ifndef NDEBUG
- visitedLiveValues.insert(originalValue);
+ VisitedLiveValues.insert(OriginalValue);
#endif
}
}
store->insertAfter(inst);
}
} else {
- assert((isa<Argument>(def) || isa<GlobalVariable>(def) ||
- isa<ConstantPointerNull>(def)) &&
- "Must be argument or global");
+ assert(isa<Argument>(def));
store->insertAfter(cast<Instruction>(alloca));
}
}
}
}
-static Function *getUseHolder(Module &M) {
- FunctionType *ftype =
- FunctionType::get(Type::getVoidTy(M.getContext()), true);
- Function *Func = cast<Function>(M.getOrInsertFunction("__tmp_use", ftype));
- return Func;
-}
-
/// Insert holders so that each Value is obviously live through the entire
-/// liftetime of the call.
+/// lifetime of the call.
static void insertUseHolderAfter(CallSite &CS, const ArrayRef<Value *> Values,
- SmallVectorImpl<CallInst *> &holders) {
+ SmallVectorImpl<CallInst *> &Holders) {
+ if (Values.empty())
+ // No values to hold live, might as well not insert the empty holder
+ return;
+
Module *M = CS.getInstruction()->getParent()->getParent()->getParent();
- Function *Func = getUseHolder(*M);
+ // Use a dummy vararg function to actually hold the values live
+ Function *Func = cast<Function>(M->getOrInsertFunction(
+ "__tmp_use", FunctionType::get(Type::getVoidTy(M->getContext()), true)));
if (CS.isCall()) {
// For call safepoints insert dummy calls right after safepoint
- BasicBlock::iterator next(CS.getInstruction());
- next++;
- CallInst *base_holder = CallInst::Create(Func, Values, "", next);
- holders.push_back(base_holder);
- } else if (CS.isInvoke()) {
- // For invoke safepooints insert dummy calls both in normal and
- // exceptional destination blocks
- InvokeInst *invoke = cast<InvokeInst>(CS.getInstruction());
- CallInst *normal_holder = CallInst::Create(
- Func, Values, "", invoke->getNormalDest()->getFirstInsertionPt());
- CallInst *unwind_holder = CallInst::Create(
- Func, Values, "", invoke->getUnwindDest()->getFirstInsertionPt());
- holders.push_back(normal_holder);
- holders.push_back(unwind_holder);
- } else
- llvm_unreachable("unsupported call type");
+ BasicBlock::iterator Next(CS.getInstruction());
+ Next++;
+ Holders.push_back(CallInst::Create(Func, Values, "", Next));
+ return;
+ }
+ // For invoke safepooints insert dummy calls both in normal and
+ // exceptional destination blocks
+ auto *II = cast<InvokeInst>(CS.getInstruction());
+ Holders.push_back(CallInst::Create(
+ Func, Values, "", II->getNormalDest()->getFirstInsertionPt()));
+ Holders.push_back(CallInst::Create(
+ Func, Values, "", II->getUnwindDest()->getFirstInsertionPt()));
}
static void findLiveReferences(
}
#endif
+ // When inserting gc.relocates for invokes, we need to be able to insert at
+ // the top of the successor blocks. See the comment on
+ // normalForInvokeSafepoint on exactly what is needed. Note that this step
+ // may restructure the CFG.
+ for (CallSite CS : toUpdate) {
+ if (!CS.isInvoke())
+ continue;
+ InvokeInst *invoke = cast<InvokeInst>(CS.getInstruction());
+ normalizeForInvokeSafepoint(invoke->getNormalDest(), invoke->getParent(),
+ P);
+ normalizeForInvokeSafepoint(invoke->getUnwindDest(), invoke->getParent(),
+ P);
+ }
+
// A list of dummy calls added to the IR to keep various values obviously
// live in the IR. We'll remove all of these when done.
SmallVector<CallInst *, 64> holders;
// gep a + 1
// safepoint 2
// br loop
- DenseSet<llvm::Value *> allInsertedDefs;
- for (size_t i = 0; i < records.size(); i++) {
- struct PartiallyConstructedSafepointRecord &info = records[i];
- allInsertedDefs.insert(info.NewInsertedDefs.begin(),
- info.NewInsertedDefs.end());
- }
-
// We insert some dummy calls after each safepoint to definitely hold live
// the base pointers which were identified for that safepoint. We'll then
// ask liveness for _every_ base inserted to see what is now live. Then we
}
toUpdate.clear(); // prevent accident use of invalid CallSites
- // In case if we inserted relocates in a different basic block than the
- // original safepoint (this can happen for invokes). We need to be sure that
- // original values were not used in any of the phi nodes at the
- // beginning of basic block containing them. Because we know that all such
- // blocks will have single predecessor we can safely assume that all phi
- // nodes have single entry (because of normalizeBBForInvokeSafepoint).
- // Just remove them all here.
- for (size_t i = 0; i < records.size(); i++) {
- Instruction *I = records[i].StatepointToken;
-
- if (InvokeInst *invoke = dyn_cast<InvokeInst>(I)) {
- FoldSingleEntryPHINodes(invoke->getNormalDest());
- assert(!isa<PHINode>(invoke->getNormalDest()->begin()));
-
- FoldSingleEntryPHINodes(invoke->getUnwindDest());
- assert(!isa<PHINode>(invoke->getUnwindDest()->begin()));
- }
- }
-
// Do all the fixups of the original live variables to their relocated selves
SmallVector<Value *, 128> live;
for (size_t i = 0; i < records.size(); i++) {
// TODO: Consider using bitvectors for liveness, the set of potentially
// interesting values should be small and easy to pre-compute.
-/// Is this value a constant consisting of entirely null values?
-static bool isConstantNull(Value *V) {
- return isa<Constant>(V) && cast<Constant>(V)->isNullValue();
-}
-
/// Compute the live-in set for the location rbegin starting from
/// the live-out set of the basic block
static void computeLiveInValues(BasicBlock::reverse_iterator rbegin,
for (Value *V : I->operands()) {
assert(!isUnhandledGCPointerType(V->getType()) &&
"support for FCA unimplemented");
- if (isHandledGCPointerType(V->getType()) && !isConstantNull(V) &&
- !isa<UndefValue>(V)) {
- // The choice to exclude null and undef is arbitrary here. Reconsider?
+ if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) {
+ // The choice to exclude all things constant here is slightly subtle.
+ // There are two idependent reasons:
+ // - We assume that things which are constant (from LLVM's definition)
+ // do not move at runtime. For example, the address of a global
+ // variable is fixed, even though it's contents may not be.
+ // - Second, we can't disallow arbitrary inttoptr constants even
+ // if the language frontend does. Optimization passes are free to
+ // locally exploit facts without respect to global reachability. This
+ // can create sections of code which are dynamically unreachable and
+ // contain just about anything. (see constants.ll in tests)
LiveTmp.insert(V);
}
}
Value *V = Phi->getIncomingValueForBlock(BB);
assert(!isUnhandledGCPointerType(V->getType()) &&
"support for FCA unimplemented");
- if (isHandledGCPointerType(V->getType()) && !isConstantNull(V) &&
- !isa<UndefValue>(V)) {
- // The choice to exclude null and undef is arbitrary here. Reconsider?
+ if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) {
LiveTmp.insert(V);
}
}
projects / oota-llvm.git / blobdiff