Index: include/llvm/IR/GlobalVariable.h =================================================================== --- include/llvm/IR/GlobalVariable.h +++ include/llvm/IR/GlobalVariable.h @@ -41,6 +41,8 @@ void setParent(Module *parent); bool isConstantGlobal : 1; // Is this a global constant? + bool isWriteOnceGlobal : 1; // Is this a writeonce value? + 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 +146,12 @@ bool isConstant() const { return isConstantGlobal; } void setConstant(bool Val) { isConstantGlobal = Val; } + bool isWriteOnce() const { return isWriteOnceGlobal;} + void setWriteOnce(bool Val) { isWriteOnceGlobal = 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,8 @@ /// class AllocaInst : public UnaryInstruction { Type *AllocatedType; + bool isWriteOnceLocal; + bool isWrittenTo; // Transient. protected: // Note: Instruction needs to be a friend here to call cloneImpl. @@ -132,6 +134,12 @@ } void setAlignment(unsigned Align); + bool isWriteOnce() const { return isWriteOnceLocal; } + void setWriteOnce(bool Val) { isWriteOnceLocal = Val; } + + 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/AsmParser/LLLexer.cpp =================================================================== --- lib/AsmParser/LLLexer.cpp +++ lib/AsmParser/LLLexer.cpp @@ -496,7 +496,7 @@ KEYWORD(true); KEYWORD(false); KEYWORD(declare); KEYWORD(define); - KEYWORD(global); KEYWORD(constant); + KEYWORD(global); KEYWORD(constant); KEYWORD(writeonce); KEYWORD(private); KEYWORD(internal); Index: lib/AsmParser/LLParser.h =================================================================== --- lib/AsmParser/LLParser.h +++ lib/AsmParser/LLParser.h @@ -272,7 +272,7 @@ bool ParseDeclare(); bool ParseDefine(); - bool ParseGlobalType(bool &IsConstant); + bool ParseGlobalType(bool &IsConstant, bool &IsWriteOnce); bool ParseUnnamedGlobal(); bool ParseNamedGlobal(); bool ParseGlobal(const std::string &Name, LocTy Loc, unsigned Linkage, Index: lib/AsmParser/LLParser.cpp =================================================================== --- lib/AsmParser/LLParser.cpp +++ lib/AsmParser/LLParser.cpp @@ -413,8 +413,8 @@ /// ParseGlobalType /// ::= 'constant' -/// ::= 'global' -bool LLParser::ParseGlobalType(bool &IsConstant) { +/// ::= 'global' OptionalWriteOnce +bool LLParser::ParseGlobalType(bool &IsConstant, bool &IsWriteOnce) { if (Lex.getKind() == lltok::kw_constant) IsConstant = true; else if (Lex.getKind() == lltok::kw_global) @@ -424,6 +424,12 @@ return TokError("expected 'global' or 'constant'"); } Lex.Lex(); + + if (!IsConstant && EatIfPresent(lltok::kw_writeonce)) + IsWriteOnce = true; + else + IsWriteOnce = false; + return false; } @@ -767,7 +773,7 @@ "symbol with local linkage must have default visibility"); unsigned AddrSpace; - bool IsConstant, IsExternallyInitialized; + bool IsConstant, IsWriteOnce, IsExternallyInitialized; LocTy IsExternallyInitializedLoc; LocTy TyLoc; @@ -776,7 +782,7 @@ ParseOptionalToken(lltok::kw_externally_initialized, IsExternallyInitialized, &IsExternallyInitializedLoc) || - ParseGlobalType(IsConstant) || + ParseGlobalType(IsConstant, IsWriteOnce) || ParseType(Ty, TyLoc)) return true; @@ -833,6 +839,7 @@ if (Init) GV->setInitializer(Init); GV->setConstant(IsConstant); + GV->setWriteOnce(IsWriteOnce); GV->setLinkage((GlobalValue::LinkageTypes)Linkage); GV->setVisibility((GlobalValue::VisibilityTypes)Visibility); GV->setDLLStorageClass((GlobalValue::DLLStorageClassTypes)DLLStorageClass); @@ -5686,6 +5693,7 @@ Type *Ty = nullptr; bool IsInAlloca = EatIfPresent(lltok::kw_inalloca); + bool IsWriteOnce = EatIfPresent(lltok::kw_writeonce); if (ParseType(Ty, TyLoc)) return true; @@ -5710,6 +5718,7 @@ AllocaInst *AI = new AllocaInst(Ty, Size, Alignment); AI->setUsedWithInAlloca(IsInAlloca); + AI->setWriteOnce(IsWriteOnce); Inst = AI; return AteExtraComma ? InstExtraComma : InstNormal; } Index: lib/AsmParser/LLToken.h =================================================================== --- lib/AsmParser/LLToken.h +++ lib/AsmParser/LLToken.h @@ -34,7 +34,7 @@ kw_x, kw_true, kw_false, kw_declare, kw_define, - kw_global, kw_constant, + kw_global, kw_constant, kw_writeonce, kw_private, kw_internal, Index: lib/IR/AsmWriter.cpp =================================================================== --- lib/IR/AsmWriter.cpp +++ lib/IR/AsmWriter.cpp @@ -2372,6 +2372,11 @@ Out << "addrspace(" << AddressSpace << ") "; if (GV->isExternallyInitialized()) Out << "externally_initialized "; Out << (GV->isConstant() ? "constant " : "global "); + if (GV->isWriteOnce()) { + assert(!GV->isConstant() && + "'constant' globals can't be 'writeonce'"); + Out << "writeonce "; + } TypePrinter.print(GV->getType()->getElementType(), Out); if (GV->hasInitializer()) { @@ -2981,6 +2986,8 @@ Out << ' '; if (AI->isUsedWithInAlloca()) Out << "inalloca "; + if (AI->isWriteOnce()) + Out << "writeonce "; TypePrinter.print(AI->getAllocatedType(), Out); // Explicitly write the array size if the code is broken, if it's an array Index: lib/IR/Globals.cpp =================================================================== --- lib/IR/Globals.cpp +++ lib/IR/Globals.cpp @@ -151,6 +151,7 @@ OperandTraits::op_begin(this), InitVal != nullptr, Link, Name, AddressSpace), isConstantGlobal(constant), + isWriteOnceGlobal(false), isWrittenTo(false), isExternallyInitializedConstant(isExternallyInitialized) { setThreadLocalMode(TLMode); if (InitVal) { @@ -169,6 +170,7 @@ OperandTraits::op_begin(this), InitVal != nullptr, Link, Name, AddressSpace), isConstantGlobal(constant), + isWriteOnceGlobal(false), 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), isWriteOnceLocal(false), 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), isWriteOnceLocal(false), isWrittenTo(false) { setAlignment(Align); assert(!Ty->isVoidTy() && "Cannot allocate void!"); setName(Name); Index: lib/Linker/LinkModules.cpp =================================================================== --- lib/Linker/LinkModules.cpp +++ lib/Linker/LinkModules.cpp @@ -1123,6 +1123,8 @@ if (DGVar && SGVar && DGVar->isDeclaration() && SGVar->isDeclaration() && (!DGVar->isConstant() || !SGVar->isConstant())) NewGVar->setConstant(false); + NewGVar->setWriteOnce(!NewGVar->isConstant() && + DGVar->isWriteOnce() && SGVar->isWriteOnce()); } // Make sure to remember this mapping. Index: lib/Transforms/IPO/FunctionAttrs.cpp =================================================================== --- lib/Transforms/IPO/FunctionAttrs.cpp +++ lib/Transforms/IPO/FunctionAttrs.cpp @@ -37,6 +37,8 @@ #include "llvm/Analysis/TargetLibraryInfo.h" using namespace llvm; +#include "llvm/Support/raw_ostream.h" // TODO: Remove! + #define DEBUG_TYPE "functionattrs" STATISTIC(NumReadNone, "Number of functions marked readnone"); @@ -156,6 +158,115 @@ 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)) { + if (GV->isWriteOnce()) { + HasWriteOnceArg = true; + assert(!GV->isConstant() && "Constants can't be writeonce"); + } + + return HasWriteOnceArg && GV->isWritten(); + } + if (AllocaInst* AI = dyn_cast(Arg)) { + if (AI->isWriteOnce()) + HasWriteOnceArg = true; + return HasWriteOnceArg && 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; +} + +/// 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(); + GlobalVariable* GV = dyn_cast(Addr); + AllocaInst* AI = dyn_cast(Addr); + if (GV && GV->isWriteOnce()) + GV->setWritten(true); + else if (AI && AI->isWriteOnce()) + AI->setWritten(true); + return; + } + else if (II->getIntrinsicID() == Intrinsic::invariant_end) { + llvm::Value *Addr = II->getArgOperand(2)->stripPointerCasts(); + GlobalVariable* GV = dyn_cast(Addr); + AllocaInst* AI = dyn_cast(Addr); + if (GV && GV->isWriteOnce() && GV->isWritten()) + GV->setWritten(false); + else if (AI && AI->isWriteOnce() && AI->isWritten()) + AI->setWritten(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 +304,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 @@ -1785,6 +1785,10 @@ DEBUG(dbgs() << "MARKING CONSTANT: " << *GV << "\n"); GV->setConstant(true); + // 'constant' globals can't be 'writeonce'. + if (GV->isWriteOnce()) + GV->setWriteOnce(false); + // Clean up any obviously simplifiable users now. CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI); @@ -2210,6 +2214,10 @@ return Invariants; } + const SmallPtrSetImpl &getReadOnlys() const { + return ReadOnlys; + } + private: Constant *ComputeLoadResult(Constant *P); @@ -2237,6 +2245,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 +2494,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 +2508,18 @@ Invariants.insert(GV); DEBUG(dbgs() << "Found a global var that is an invariant: " << *GV << "\n"); + } + else if (GV->isWriteOnce()) { + 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 that is a non-readonly writeonce: " << *GV + << "\n"); + } + } else { DEBUG(dbgs() << "Found a global var, but can not treat it as an " "invariant.\n"); @@ -2619,6 +2643,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 +2742,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"); @@ -2704,8 +2803,18 @@ Eval.getMutatedMemory().begin(), E = Eval.getMutatedMemory().end(); I != E; ++I) CommitValueTo(I->second, I->first); - for (GlobalVariable *GV : Eval.getInvariants()) + for (GlobalVariable *GV : Eval.getInvariants()) { GV->setConstant(true); + + // 'constant' globals can't be 'writeonce'. + if (GV->isWriteOnce()) + GV->setWriteOnce(false); + } + + for (GlobalVariable *GV : Eval.getReadOnlys()) { + assert(GV->isWriteOnce() && 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); } Index: lib/Transforms/Utils/CloneModule.cpp =================================================================== --- lib/Transforms/Utils/CloneModule.cpp +++ lib/Transforms/Utils/CloneModule.cpp @@ -58,6 +58,7 @@ (GlobalVariable*) nullptr, I->getThreadLocalMode(), I->getType()->getAddressSpace()); + GV->setWriteOnce(!GV->isConstant() && I->isWriteOnce()); GV->copyAttributesFrom(I); VMap[I] = GV; } Index: lib/Transforms/Utils/CtorUtils.cpp =================================================================== --- lib/Transforms/Utils/CtorUtils.cpp +++ lib/Transforms/Utils/CtorUtils.cpp @@ -52,6 +52,7 @@ CA, "", GCL->getThreadLocalMode()); GCL->getParent()->getGlobalList().insert(GCL, NGV); NGV->takeName(GCL); + NGV->setWriteOnce(!NGV->isConstant() && GCL->isWriteOnce()); // Nuke the old list, replacing any uses with the new one. if (!GCL->use_empty()) {