Index: include/llvm/IR/GlobalVariable.h =================================================================== --- include/llvm/IR/GlobalVariable.h +++ include/llvm/IR/GlobalVariable.h @@ -41,6 +41,7 @@ void setParent(Module *parent); bool isConstantGlobal : 1; // Is this a global constant? + bool isWrittenTo : 1; // Transient -- Has this been written to? bool isExternallyInitializedConstant : 1; // Is this a global whose value // can change from its initial // value before global @@ -144,6 +145,9 @@ bool isConstant() const { return isConstantGlobal; } void setConstant(bool Val) { isConstantGlobal = Val; } + bool isWritten() const { return isWrittenTo;} + void setWritten(bool Val) { isWrittenTo = Val; } + bool isExternallyInitialized() const { return isExternallyInitializedConstant; } Index: include/llvm/IR/Instructions.h =================================================================== --- include/llvm/IR/Instructions.h +++ include/llvm/IR/Instructions.h @@ -75,6 +75,7 @@ /// class AllocaInst : public UnaryInstruction { Type *AllocatedType; + bool isWrittenTo; // Transient. protected: // Note: Instruction needs to be a friend here to call cloneImpl. @@ -132,6 +133,9 @@ } void setAlignment(unsigned Align); + bool isWritten() const { return isWrittenTo; } + void setWritten(bool Val) { isWrittenTo = Val; } + /// isStaticAlloca - Return true if this alloca is in the entry block of the /// function and is a constant size. If so, the code generator will fold it /// into the prolog/epilog code, so it is basically free. Index: include/llvm/Transforms/IPO.h =================================================================== --- include/llvm/Transforms/IPO.h +++ include/llvm/Transforms/IPO.h @@ -25,6 +25,7 @@ class Function; class BasicBlock; class GlobalValue; +class Instruction; //===----------------------------------------------------------------------===// // @@ -210,6 +211,8 @@ /// to bitsets. ModulePass *createLowerBitSetsPass(); +void markWriteOnceReadonly(Instruction* I); + //===----------------------------------------------------------------------===// // SampleProfilePass - Loads sample profile data from disk and generates // IR metadata to reflect the profile. Index: lib/Analysis/AliasAnalysis.cpp =================================================================== --- lib/Analysis/AliasAnalysis.cpp +++ lib/Analysis/AliasAnalysis.cpp @@ -105,6 +105,14 @@ const Value *Arg = *AI; if (!Arg->getType()->isPointerTy()) continue; + + // FIXME: Avoid this. Temporary workaround. + // CS must be an invariant.end() call. + if (const IntrinsicInst *II = dyn_cast(Arg)) { + if (II->getIntrinsicID() == Intrinsic::invariant_start) + continue; + } + unsigned ArgIdx = std::distance(CS.arg_begin(), AI); MemoryLocation ArgLoc = MemoryLocation::getForArgument(CS, ArgIdx, *TLI); Index: lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- lib/Analysis/BasicAliasAnalysis.cpp +++ lib/Analysis/BasicAliasAnalysis.cpp @@ -713,6 +713,14 @@ if (isAssumeIntrinsic(CS)) return MRI_NoModRef; + // FIXME: Avoid this? Temporary workaround. + if (const IntrinsicInst *II = + dyn_cast(CS.getInstruction())) { + if (II->getIntrinsicID() == Intrinsic::invariant_start || + II->getIntrinsicID() == Intrinsic::invariant_end) + return MRI_NoModRef; + } + // The AliasAnalysis base class has some smarts, lets use them. return AliasAnalysis::getModRefInfo(CS, Loc); } Index: lib/IR/Globals.cpp =================================================================== --- lib/IR/Globals.cpp +++ lib/IR/Globals.cpp @@ -150,7 +150,7 @@ : GlobalObject(Ty, Value::GlobalVariableVal, OperandTraits::op_begin(this), InitVal != nullptr, Link, Name, AddressSpace), - isConstantGlobal(constant), + isConstantGlobal(constant), isWrittenTo(false), isExternallyInitializedConstant(isExternallyInitialized) { setThreadLocalMode(TLMode); if (InitVal) { @@ -168,7 +168,7 @@ : GlobalObject(Ty, Value::GlobalVariableVal, OperandTraits::op_begin(this), InitVal != nullptr, Link, Name, AddressSpace), - isConstantGlobal(constant), + isConstantGlobal(constant), isWrittenTo(false), isExternallyInitializedConstant(isExternallyInitialized) { setThreadLocalMode(TLMode); if (InitVal) { Index: lib/IR/Instructions.cpp =================================================================== --- lib/IR/Instructions.cpp +++ lib/IR/Instructions.cpp @@ -1163,7 +1163,7 @@ const Twine &Name, Instruction *InsertBefore) : UnaryInstruction(PointerType::getUnqual(Ty), Alloca, getAISize(Ty->getContext(), ArraySize), InsertBefore), - AllocatedType(Ty) { + AllocatedType(Ty), isWrittenTo(false) { setAlignment(Align); assert(!Ty->isVoidTy() && "Cannot allocate void!"); setName(Name); @@ -1173,7 +1173,7 @@ const Twine &Name, BasicBlock *InsertAtEnd) : UnaryInstruction(PointerType::getUnqual(Ty), Alloca, getAISize(Ty->getContext(), ArraySize), InsertAtEnd), - AllocatedType(Ty) { + AllocatedType(Ty), isWrittenTo(false) { setAlignment(Align); assert(!Ty->isVoidTy() && "Cannot allocate void!"); setName(Name); Index: lib/Transforms/IPO/FunctionAttrs.cpp =================================================================== --- lib/Transforms/IPO/FunctionAttrs.cpp +++ lib/Transforms/IPO/FunctionAttrs.cpp @@ -156,6 +156,118 @@ Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } +// FIXME: Move in llvm::Value and propagate writeonce through +// different instructions. +static bool isWriteOnce(Value* Arg, bool& HasWriteOnceArg) { + + // Call sites should have been marked by now. + // So, do not traverse their arguments here. + // FIXME: other instructions that could be readonly? + CallSite CS(cast(Arg)); + if (CS) + return CS.onlyReadsMemory(); + + if (GlobalVariable* GV = dyn_cast(Arg)) { + HasWriteOnceArg = !GV->isConstant(); + return GV->isWritten(); + } + if (AllocaInst* AI = dyn_cast(Arg)) { + HasWriteOnceArg = true; + return AI->isWritten(); + } + + // Only mark pointer-type arguments + if (!Arg->getType()->isPointerTy()) + return true; + + // FIXME: A special case for constants that are not writeonce; because + // not all operands ought to be checked in the more general case below. + if (dyn_cast(Arg) && !dyn_cast(Arg)) + return true; + + // FIXME: Not all operands ought to be checked here. + // Some may have already been processed (see above)... + if (User* U = dyn_cast(Arg)) { + auto Ops = U->operands(); + for(auto Op = Ops.begin(), OpEnd = Ops.end(); Op != OpEnd; ++Op) { + if (isWriteOnce(Op->get(), HasWriteOnceArg)) + continue; + return false; + } + return HasWriteOnceArg; + } + + // FIXME: Handle other Value kinds: Argument, BasicBlock, InlineAsm, etc... + return false; +} + +// FIXME: Move to llvm::Value? +static bool isWritten(Value* Arg) { + if (GlobalVariable* GV = dyn_cast(Arg)) + return GV->isWritten(); + if (AllocaInst* AI = dyn_cast(Arg)) + return AI->isWritten(); + return false; +} + +// FIXME: Move to llvm::Value? +static void setWritten(Value* Arg, bool Val) { + if (GlobalVariable* GV = dyn_cast(Arg)) + GV->setWritten(Val); + if (AllocaInst* AI = dyn_cast(Arg)) + AI->setWritten(Val); +} + +/// Mark call instructions readonly, based on the writeonceness of +/// their arguments. +/// NOTE: AA->getModRefBehavior(CS) only cares about callee not call arguments. +void llvm::markWriteOnceReadonly(Instruction* I) { + assert(I && "Can't mark a null instruction."); + + // Process @llvm.invariant.start/end intrinsics. + if (IntrinsicInst *II = dyn_cast(I)) { + if (II->getIntrinsicID() == Intrinsic::invariant_start) { + llvm::Value *Addr = II->getArgOperand(1)->stripPointerCasts(); + setWritten(Addr, true); + return; + } + else if (II->getIntrinsicID() == Intrinsic::invariant_end) { + llvm::Value *Addr = II->getArgOperand(2)->stripPointerCasts(); + if (isWritten(Addr)) + setWritten(Addr, false); + return; + } + } + + // FIXME: Only Call instructions for now. Extend CallSite API. + CallSite CS(cast(I)); + CallInst* CI = dyn_cast(I); + if (CI && !CS.onlyReadsMemory()) { + + // Mark writeonce arguments readonly + bool hasAllReadOnlyArgs = true; + for(unsigned ArgNo = 0; ArgNo < CI->getNumArgOperands(); ++ArgNo) { + Value* Arg = CI->getArgOperand(ArgNo); + + if (CI->paramHasAttr(ArgNo + 1, Attribute::ReadOnly)) + continue; + + // Mark readonly, if not already marked + bool markReadOnly = false; + if (isWriteOnce(Arg, markReadOnly)) { + if (markReadOnly) + CI->addAttribute(ArgNo + 1, Attribute::ReadOnly); + continue; + } + hasAllReadOnlyArgs = false; + } + + // If all arguments are readonly, the call site is readonly + // FIXME: Not always. + if (hasAllReadOnlyArgs && CI->getNumArgOperands()) + CI->setOnlyReadsMemory(); + } +} /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { @@ -193,6 +305,20 @@ continue; } + // Scan the function body to mark call instructions readonly, based on + // the writeonceness of their arguments. + // FIXME: Move into a separate pass? + for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { + Instruction *I = &*II; + + // Ignore calls to functions in the same SCC. + CallSite CS(cast(I)); + if (CS && CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction())) + continue; + + markWriteOnceReadonly(I); + } + // Scan the function body for instructions that may read or write memory. for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { Instruction *I = &*II; Index: lib/Transforms/IPO/GlobalOpt.cpp =================================================================== --- lib/Transforms/IPO/GlobalOpt.cpp +++ lib/Transforms/IPO/GlobalOpt.cpp @@ -2210,6 +2210,10 @@ return Invariants; } + const SmallPtrSetImpl &getReadOnlys() const { + return ReadOnlys; + } + private: Constant *ComputeLoadResult(Constant *P); @@ -2237,6 +2241,10 @@ /// static constructor. SmallPtrSet Invariants; + /// ReadOnlys - These global variables are writeonce variables that + /// have been marked readonly by the static constructor. + SmallPtrSet ReadOnlys; + /// SimpleConstants - These are constants we have checked and know to be /// simple enough to live in a static initializer of a global. SmallPtrSet SimpleConstants; @@ -2482,7 +2490,7 @@ // We don't insert an entry into Values, as it doesn't have a // meaningful return value. if (!II->use_empty()) { - DEBUG(dbgs() << "Found unused invariant_start. Can't evaluate.\n"); + DEBUG(dbgs() << "Found used invariant_start. Can't evaluate.\n"); return false; } ConstantInt *Size = cast(II->getArgOperand(0)); @@ -2496,6 +2504,11 @@ Invariants.insert(GV); DEBUG(dbgs() << "Found a global var that is an invariant: " << *GV << "\n"); + } + else if (GV->isWritten()) { + ReadOnlys.insert(GV); + DEBUG(dbgs() << "Found a global var that is a readonly writeonce: " << *GV + << "\n"); } else { DEBUG(dbgs() << "Found a global var, but can not treat it as an " "invariant.\n"); @@ -2619,6 +2632,77 @@ } } +void markWriteOnceReadonly(Evaluator &Eval, Function *F) { + + // Scan the block to mark call instructions readonly, based on + // the writeonceness of their arguments. + BasicBlock *BB = F->begin(); + while (BB) { + DEBUG(dbgs() << "Marking writeonce instructions in BB readonly: " << *BB << "\n"); + + BasicBlock* NextBB = nullptr; + BasicBlock::iterator CurInst = BB->begin(); + + while (CurInst) { + DEBUG(dbgs() << "Marking writeonce instruction readonly: " << *CurInst << "\n"); + + markWriteOnceReadonly(CurInst); + + if (isa(CurInst) || isa(CurInst)) { + CallSite CS(CurInst); + + // Debug info, inline asm, intrinsics, ... + // can safely be ignored here. + if (isa(CS.getInstruction()) || + isa(CS.getCalledValue()) || + dyn_cast(CS.getInstruction())) { + ++CurInst; + continue; + } + + Function *Callee = dyn_cast(Eval.getVal(CS.getCalledValue())); + if (!Callee || Callee->mayBeOverridden()) + break; + + if (!Callee->isDeclaration() && + !Callee->getFunctionType()->isVarArg()) { + markWriteOnceReadonly(Eval, Callee); + } + } else if (isa(CurInst)) { + if (BranchInst *BI = dyn_cast(CurInst)) { + if (BI->isUnconditional()) { + NextBB = BI->getSuccessor(0); + } else { + if (ConstantInt *Cond = + dyn_cast(Eval.getVal(BI->getCondition()))) + NextBB = BI->getSuccessor(!Cond->getZExtValue()); + } + } else if (SwitchInst *SI = dyn_cast(CurInst)) { + if(ConstantInt *Val = + dyn_cast(Eval.getVal(SI->getCondition()))) + NextBB = SI->findCaseValue(Val).getCaseSuccessor(); + } else if (IndirectBrInst *IBI = dyn_cast(CurInst)) { + Value *Val = Eval.getVal(IBI->getAddress())->stripPointerCasts(); + if (BlockAddress *BA = dyn_cast(Val)) + NextBB = BA->getBasicBlock(); + NextBB = nullptr; + } else if (isa(CurInst)) + NextBB = nullptr; + break; + } + + if (InvokeInst *II = dyn_cast(CurInst)) { + NextBB = II->getNormalDest(); + break; + } + + ++CurInst; + } + + BB = NextBB; + } +} + /// EvaluateFunction - Evaluate a call to function F, returning true if /// successful, false if we can't evaluate it. ActualArgs contains the formal /// arguments for the function. @@ -2647,6 +2731,10 @@ BasicBlock::iterator CurInst = CurBB->begin(); + // Scan the block to mark call instructions readonly, based on + // the writeonceness of their arguments. + markWriteOnceReadonly(*this, F); + while (1) { BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings. DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n"); @@ -2706,6 +2794,11 @@ CommitValueTo(I->second, I->first); for (GlobalVariable *GV : Eval.getInvariants()) GV->setConstant(true); + + for (GlobalVariable *GV : Eval.getReadOnlys()) { + assert(GV->isWritten() && + "Only readonly writeonce global vars are allowed here."); + } } return EvalSuccess; Index: lib/Transforms/InstCombine/InstructionCombining.cpp =================================================================== --- lib/Transforms/InstCombine/InstructionCombining.cpp +++ lib/Transforms/InstCombine/InstructionCombining.cpp @@ -1952,6 +1952,17 @@ uint64_t DontKnow = CI->isZero() ? -1ULL : 0; ReplaceInstUsesWith(*I, ConstantInt::get(I->getType(), DontKnow)); } + + // If this is a paired *.invariant.start, then erase it's *.end. + if (II->getIntrinsicID() == Intrinsic::invariant_start && + !I->use_empty()) { + IntrinsicInst *User = + dyn_cast(cast(*I->user_begin())); + assert(I->hasOneUse() && User && + User->getIntrinsicID() == Intrinsic::invariant_end && + "The paired instruction should be an invariant_end."); + EraseInstFromFunction(*User); + } } EraseInstFromFunction(*I); }