Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -628,6 +628,9 @@ /// nodes. bool isImplicit() const { return !isExplicit(); } + /// @brief is this MemoryAccess representing a use or def of an llvm::Value? + bool isScalar() const { return Origin == SCALAR; } + /// @brief Is this MemoryAccess modeling special PHI node accesses? bool isPHI() const { return Origin == PHI; } @@ -739,9 +742,15 @@ typedef SmallVector MemoryAccessVec; MemoryAccessVec MemAccs; - /// @brief Mapping from instructions to (scalar) memory accesses. + /// @brief Mapping from instructions to explicit memory accesses. DenseMap InstructionToAccess; + /// @brief Implicit loads at the beginning of a statement. + MemoryAccessVec LeadingReads; + + /// @bried Implicit stores at the end of a statement. + MemoryAccessVec TrailingWrites; + //@} /// @brief A SCoP statement represents either a basic block (affine/precise @@ -870,30 +879,40 @@ /// @brief Return true if this statement does not contain any accesses. bool isEmpty() const { return MemAccs.empty(); } - /// @brief Return the (scalar) memory accesses for @p Inst. + /// @brief Return the vector of leading implicit loads. + const MemoryAccessVec &getLeadingReads() const { return LeadingReads; } + + /// @brief Return the vector of trailing implicit stores. + const MemoryAccessVec &getTrailingWrites() const { return TrailingWrites; } + + /// @brief Return the explicit memory accesses for @p Inst. const MemoryAccessList &getAccessesFor(const Instruction *Inst) const { MemoryAccessList *MAL = lookupAccessesFor(Inst); assert(MAL && "Cannot get memory accesses because they do not exist!"); return *MAL; } - /// @brief Return the (scalar) memory accesses for @p Inst if any. + /// @brief Return the explicit memory accesses for @p Inst if any. MemoryAccessList *lookupAccessesFor(const Instruction *Inst) const { auto It = InstructionToAccess.find(Inst); - return It == InstructionToAccess.end() ? nullptr : It->getSecond(); + if (It == InstructionToAccess.end()) + return nullptr; + return It->getSecond()->empty() ? nullptr : It->getSecond(); } - /// @brief Return the __first__ (scalar) memory access for @p Inst. + /// @brief Return the explicit memory access for @p Inst. const MemoryAccess &getAccessFor(const Instruction *Inst) const { MemoryAccess *MA = lookupAccessFor(Inst); assert(MA && "Cannot get memory access because it does not exist!"); return *MA; } - /// @brief Return the __first__ (scalar) memory access for @p Inst if any. + /// @brief Return the explicit memory access for @p Inst if any. MemoryAccess *lookupAccessFor(const Instruction *Inst) const { auto It = InstructionToAccess.find(Inst); - return It == InstructionToAccess.end() ? nullptr : It->getSecond()->front(); + if (It == InstructionToAccess.end()) + return nullptr; + return It->getSecond()->empty() ? nullptr : It->getSecond()->front(); } void setBasicBlock(BasicBlock *Block) { @@ -904,7 +923,13 @@ } /// @brief Add @p Access to this statement's list of accesses. - void addAccess(MemoryAccess *Access); + void addExplicitAccess(MemoryAccess *Access); + + /// @brief Add @p Access to this statement's list of implicit loads. + void addLeadingLoad(MemoryAccess *Access); + + /// @brief Add @p Access to this statement's list of implicit stores. + void addTrailingWrite(MemoryAccess *Access); /// @brief Move the memory access in @p InvMAs to @p TargetList. /// @@ -1666,12 +1691,16 @@ /// @param Subscripts Access subscripts per dimension. /// @param Sizes The array diminsion's sizes. /// @param Origin Purpose of this access. - void addMemoryAccess(BasicBlock *BB, Instruction *Inst, - MemoryAccess::AccessType Type, Value *BaseAddress, - unsigned ElemBytes, bool Affine, Value *AccessValue, - ArrayRef Subscripts, - ArrayRef Sizes, - MemoryAccess::AccessOrigin Origin); + /// + /// @return The newly created MemoryAccess instance or NULL if the access + /// would have no effect. + MemoryAccess *addMemoryAccess(BasicBlock *BB, Instruction *Inst, + MemoryAccess::AccessType Type, + Value *BaseAddress, unsigned ElemBytes, + bool Affine, Value *AccessValue, + ArrayRef Subscripts, + ArrayRef Sizes, + MemoryAccess::AccessOrigin Origin); /// @brief Create a MemoryAccess that represents either a LoadInst or /// StoreInst. Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -826,7 +826,8 @@ } } -void ScopStmt::addAccess(MemoryAccess *Access) { +void ScopStmt::addExplicitAccess(MemoryAccess *Access) { + assert(Access->isExplicit()); Instruction *AccessInst = Access->getAccessInstruction(); MemoryAccessList *&MAL = InstructionToAccess[AccessInst]; @@ -836,6 +837,22 @@ MemAccs.push_back(MAL->front()); } +void ScopStmt::addLeadingLoad(MemoryAccess *Access) { + assert(Access->isImplicit()); + assert(Access->isRead()); + + LeadingReads.push_back(Access); + MemAccs.push_back(Access); +} + +void ScopStmt::addTrailingWrite(MemoryAccess *Access) { + assert(Access->isImplicit()); + assert(Access->isWrite()); + + TrailingWrites.push_back(Access); + MemAccs.push_back(Access); +} + void ScopStmt::realignParams() { for (MemoryAccess *MA : *this) MA->realignParams(); @@ -1358,28 +1375,24 @@ void ScopStmt::hoistMemoryAccesses(MemoryAccessList &InvMAs, InvariantAccessesTy &TargetList) { - // Remove all memory accesses in @p InvMAs from this statement together - // with all scalar accesses that were caused by them. The tricky iteration - // order uses is needed because the MemAccs is a vector and the order in - // which the accesses of each memory access list (MAL) are stored in this - // vector is reversed. + // Remove the MemoryAccess from all lists. for (MemoryAccess *MA : InvMAs) { - auto &MAL = *lookupAccessesFor(MA->getAccessInstruction()); - MAL.reverse(); + assert(MA->isExplicit() && MA->isRead()); - auto MALIt = MAL.begin(); - auto MALEnd = MAL.end(); - auto MemAccsIt = MemAccs.begin(); - while (MALIt != MALEnd) { - while (*MemAccsIt != *MALIt) - MemAccsIt++; - - MALIt++; - MemAccs.erase(MemAccsIt); - } - - InstructionToAccess.erase(MA->getAccessInstruction()); - delete &MAL; + // Remove the access itself and the potential scalar write if used ouside of + // this statement. + auto &MAL = *lookupAccessesFor(MA->getAccessInstruction()); + MAL.remove(MA); + auto Predicate = [MA](MemoryAccess *Acc) -> bool { + return Acc == MA || + Acc->isScalar() && Acc->isWrite() && + Acc->getAccessValue() == MA->getAccessValue(); + }; + MemAccs.erase(std::remove_if(MemAccs.begin(), MemAccs.end(), Predicate), + MemAccs.end()); + TrailingWrites.erase( + std::remove_if(TrailingWrites.begin(), TrailingWrites.end(), Predicate), + TrailingWrites.end()); } // Get the context under which this statement, hence the memory accesses, are @@ -3384,19 +3397,19 @@ } } -void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst, - MemoryAccess::AccessType Type, - Value *BaseAddress, unsigned ElemBytes, - bool Affine, Value *AccessValue, - ArrayRef Subscripts, - ArrayRef Sizes, - MemoryAccess::AccessOrigin Origin) { +MemoryAccess *ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst, + MemoryAccess::AccessType Type, + Value *BaseAddress, unsigned ElemBytes, + bool Affine, Value *AccessValue, + ArrayRef Subscripts, + ArrayRef Sizes, + MemoryAccess::AccessOrigin Origin) { ScopStmt *Stmt = scop->getStmtForBasicBlock(BB); // Do not create a memory access for anything not in the SCoP. It would be // ignored anyway. if (!Stmt) - return; + return nullptr; AccFuncSetType &AccList = AccFuncMap[BB]; size_t Identifier = AccList.size(); @@ -3414,7 +3427,7 @@ AccList.emplace_back(Stmt, Inst, Id, Type, BaseAddress, ElemBytes, Affine, Subscripts, Sizes, AccessValue, Origin, BaseName); - Stmt->addAccess(&AccList.back()); + return &AccList.back(); } void ScopInfo::addExplicitAccess( @@ -3423,38 +3436,52 @@ ArrayRef Sizes, Value *AccessValue) { assert(isa(MemAccInst) || isa(MemAccInst)); assert(isa(MemAccInst) == (Type == MemoryAccess::READ)); - addMemoryAccess(MemAccInst->getParent(), MemAccInst, Type, BaseAddress, - ElemBytes, IsAffine, AccessValue, Subscripts, Sizes, - MemoryAccess::EXPLICIT); + MemoryAccess *Acc = addMemoryAccess( + MemAccInst->getParent(), MemAccInst, Type, BaseAddress, ElemBytes, + IsAffine, AccessValue, Subscripts, Sizes, MemoryAccess::EXPLICIT); + if (Acc) + Acc->getStatement()->addExplicitAccess(Acc); } void ScopInfo::addScalarWriteAccess(Instruction *Value) { - addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, 1, - true, Value, ArrayRef(), - ArrayRef(), MemoryAccess::SCALAR); + MemoryAccess *Acc = + addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, + Value, 1, true, Value, ArrayRef(), + ArrayRef(), MemoryAccess::SCALAR); + if (Acc) + Acc->getStatement()->addTrailingWrite(Acc); } void ScopInfo::addScalarReadAccess(Value *Value, Instruction *User) { assert(!isa(User)); - addMemoryAccess(User->getParent(), User, MemoryAccess::READ, Value, 1, true, - Value, ArrayRef(), ArrayRef(), - MemoryAccess::SCALAR); + MemoryAccess *Acc = addMemoryAccess( + User->getParent(), User, MemoryAccess::READ, Value, 1, true, Value, + ArrayRef(), ArrayRef(), MemoryAccess::SCALAR); + if (Acc) + Acc->getStatement()->addLeadingLoad(Acc); } void ScopInfo::addScalarReadAccess(Value *Value, PHINode *User, BasicBlock *UserBB) { - addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, 1, true, Value, - ArrayRef(), ArrayRef(), - MemoryAccess::SCALAR); + MemoryAccess *Acc = addMemoryAccess( + UserBB, User, MemoryAccess::READ, Value, 1, true, Value, + ArrayRef(), ArrayRef(), MemoryAccess::SCALAR); + if (Acc) + Acc->getStatement()->addLeadingLoad(Acc); } void ScopInfo::addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock, Value *IncomingValue, bool IsExitBlock) { - addMemoryAccess(IncomingBlock, IncomingBlock->getTerminator(), - MemoryAccess::MUST_WRITE, PHI, 1, true, IncomingValue, - ArrayRef(), ArrayRef(), - IsExitBlock ? MemoryAccess::SCALAR : MemoryAccess::PHI); + MemoryAccess *Acc = + addMemoryAccess(IncomingBlock, IncomingBlock->getTerminator(), + MemoryAccess::MUST_WRITE, PHI, 1, true, IncomingValue, + ArrayRef(), ArrayRef(), + IsExitBlock ? MemoryAccess::SCALAR : MemoryAccess::PHI); + if (Acc) + Acc->getStatement()->addTrailingWrite(Acc); } void ScopInfo::addPHIReadAccess(PHINode *PHI) { - addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI, - ArrayRef(), ArrayRef(), - MemoryAccess::PHI); + MemoryAccess *Acc = addMemoryAccess( + PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI, + ArrayRef(), ArrayRef(), MemoryAccess::PHI); + if (Acc) + Acc->getStatement()->addLeadingLoad(Acc); } void ScopInfo::buildScop(Region &R, DominatorTree &DT) { Index: lib/CodeGen/BlockGenerators.cpp =================================================================== --- lib/CodeGen/BlockGenerators.cpp +++ lib/CodeGen/BlockGenerators.cpp @@ -424,9 +424,9 @@ } void BlockGenerator::generateScalarLoads(ScopStmt &Stmt, ValueMapT &BBMap) { - for (MemoryAccess *MA : Stmt) { - if (MA->isExplicit() || MA->isWrite()) - continue; + for (MemoryAccess *MA : Stmt.getLeadingReads()) { + assert(MA->isImplicit()); + assert(MA->isRead()); auto *Address = getOrCreateAlloca(*MA); BBMap[MA->getBaseAddr()] = @@ -489,9 +489,9 @@ "generateScalarStores() function in the " "RegionGenerator"); - for (MemoryAccess *MA : Stmt) { - if (MA->isExplicit() || MA->isRead()) - continue; + for (MemoryAccess *MA : Stmt.getTrailingWrites()) { + assert(MA->isImplicit()); + assert(MA->isWrite()); Value *Val = MA->getAccessValue(); auto *Address = getOrCreateAlloca(*MA); @@ -1134,7 +1134,7 @@ void RegionGenerator::generateScalarLoads(ScopStmt &Stmt, ValueMapT &BBMap) { Region &R = Stmt.getParent()->getRegion(); - for (MemoryAccess *MA : Stmt) { + for (MemoryAccess *MA : Stmt.getLeadingReads()) { if (MA->isExplicit() || MA->isWrite()) continue; @@ -1161,9 +1161,9 @@ // This statement's region exit block, not the scop's exit. BasicBlock *StmtExitBB = Stmt.getRegion()->getExit(); - for (MemoryAccess *MA : Stmt) { - if (MA->isExplicit() || MA->isRead()) - continue; + for (MemoryAccess *MA : Stmt.getTrailingWrites()) { + assert(MA->isImplicit()); + assert(MA->isWrite()); Instruction *ScalarInst = MA->getAccessInstruction(); Value *Val = MA->getAccessValue();