Index: polly/trunk/include/polly/Support/VirtualInstruction.h =================================================================== --- polly/trunk/include/polly/Support/VirtualInstruction.h +++ polly/trunk/include/polly/Support/VirtualInstruction.h @@ -0,0 +1,168 @@ +//===------ VirtualInstruction.cpp ------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Tools for determining which instructions are within a statement and the +// nature of their operands. +// +//===----------------------------------------------------------------------===// + +#ifndef POLLY_SUPPORT_VIRTUALINSTRUCTION_H +#define POLLY_SUPPORT_VIRTUALINSTRUCTION_H + +#include "polly/ScopInfo.h" + +namespace polly { + +/// Determine the nature of a value's use within a statement. +/// +/// These are not always representable by llvm::Use. For instance, scalar write +/// MemoryAccesses do use a value, but are not associated with an instruction's +/// argument. +/// +/// Despite its name it is not tied to virtual instructions (although it works +/// fine with them), but to promote consistent handling of values used in +/// statements. +class VirtualUse { +public: + /// The different types of uses. Handling usually differentiates a lot between + /// these; one can use a switch to handle each case (and get warned by the + /// compiler if one is not handled). + enum UseKind { + // An llvm::Constant. + Constant, + + // An llvm::BasicBlock. + Block, + + // A value that can be generated using ScopExpander. + Synthesizable, + + // A load that always reads the same value throughout the SCoP (address and + // the value located there a SCoP-invariant) and has been hoisted in front + // of the SCoP. + Hoisted, + + // Definition before the SCoP and not synthesizable. Can be an instruction + // outside the SCoP, a function argument or a global value. Whether there is + // a scalar MemoryAccess in this statement for reading it depends on the + // -polly-analyze-read-only-scalars switch. + ReadOnly, + + // A definition within the same statement. No MemoryAccess between + // definition and use are necessary. + Intra, + + // Definition in another statement. There is a scalar MemoryAccess that + // makes it available in this statement. + Inter + }; + +private: + /// The statement where a value is used. + ScopStmt *User; + + /// The value that is used. + Value *Val; + + /// The type of value use. + UseKind Kind; + + /// The value represented as llvm::SCEV expression. + const SCEV *ScevExpr; + + /// If this is an inter-statement (or read-only) use, contains the + /// MemoryAccess that makes the value available in this statement. In case of + /// intra-statement uses, can contain a MemoryKind::Array access. In all other + /// cases, it is a nullptr. + MemoryAccess *InputMA; + + VirtualUse(ScopStmt *User, Value *Val, UseKind Kind, const SCEV *ScevExpr, + MemoryAccess *InputMA) + : User(User), Val(Val), Kind(Kind), ScevExpr(ScevExpr), InputMA(InputMA) { + } + +public: + /// Get a VirtualUse for an llvm::Use. + /// + /// @param S The Scop object. + /// @param U The llvm::Use the get information for. + /// @param LI The LoopInfo analysis. Needed to determine whether the + /// value is synthesizable. + /// @param Virtual Whether to ignore existing MemoryAcccess. + /// + /// @return The VirtualUse representing the same use as @p U. + static VirtualUse create(Scop *S, Use &U, LoopInfo *LI, bool Virtual); + + /// Get a VirtualUse for any kind of use of a value within a statement. + /// + /// @param S The Scop object. + /// @param UserStmt The statement in which @p Val is used. Can be nullptr, in + /// which case it assumed that the statement has been + /// removed, which is only possible if no instruction in it + /// had side-effects or computes a value used by another + /// statement. + /// @param UserScope Loop scope in which the value is used. Needed to + /// determine whether the value is synthesizable. + /// @param Val The value being used. + /// @param Virtual Whether to use (and prioritize over instruction location) + /// information about MemoryAccesses. + /// + /// @return A VirtualUse object that gives information about @p Val's use in + /// @p UserStmt. + static VirtualUse create(Scop *S, ScopStmt *UserStmt, Loop *UserScope, + Value *Val, bool Virtual); + + static VirtualUse create(ScopStmt *UserStmt, Loop *UserScope, Value *Val, + bool Virtual) { + return create(UserStmt->getParent(), UserStmt, UserScope, Val, Virtual); + } + + bool isConstant() const { return Kind == Constant; } + bool isBlock() const { return Kind == Block; } + bool isSynthesizable() const { return Kind == Synthesizable; } + bool isHoisted() const { return Kind == Hoisted; } + bool isReadOnly() const { return Kind == ReadOnly; } + bool isIntra() const { return Kind == Intra; } + bool isInter() const { return Kind == Inter; } + + /// Return user statement. + ScopStmt *getUser() const { return User; } + + /// Return the used value. + llvm::Value *getValue() const { return Val; } + + /// Return the type of use. + UseKind getKind() const { return Kind; } + + /// Return the ScalarEvolution representation of @p Val. + const SCEV *getScevExpr() const { return ScevExpr; } + + /// Return the MemoryAccess that makes the value available in this statement, + /// if any. + MemoryAccess *getMemoryAccess() const { return InputMA; } + + /// Print a description of this object. + /// + /// @param OS Stream to print to. + /// @param Reproducible If true, ensures that the output is stable between + /// runs and is suitable to check in regression tests. This excludes printing + /// e.g. pointer values. + /// If false, the output should not be used for regression + /// tests, but may contain more information useful in + /// debugger sessions. + void print(raw_ostream &OS, bool Reproducible = true) const; + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + void dump() const; +#endif +}; + +} // namespace polly + +#endif /* POLLY_SUPPORT_VIRTUALINSTRUCTION_H */ Index: polly/trunk/lib/Analysis/ScopBuilder.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopBuilder.cpp +++ polly/trunk/lib/Analysis/ScopBuilder.cpp @@ -18,6 +18,7 @@ #include "polly/Options.h" #include "polly/Support/GICHelper.h" #include "polly/Support/SCEVValidator.h" +#include "polly/Support/VirtualInstruction.h" #include "llvm/Analysis/RegionIterator.h" #include "llvm/IR/DiagnosticInfo.h" @@ -553,54 +554,40 @@ } void ScopBuilder::ensureValueRead(Value *V, BasicBlock *UserBB) { - - // There cannot be an "access" for literal constants. BasicBlock references - // (jump destinations) also never change. - if ((isa(V) && !isa(V)) || isa(V)) - return; - - // If the instruction can be synthesized and the user is in the region we do - // not need to add a value dependences. - auto *Scope = LI.getLoopFor(UserBB); - if (canSynthesize(V, *scop, &SE, Scope)) - return; - - // Do not build scalar dependences for required invariant loads as we will - // hoist them later on anyway or drop the SCoP if we cannot. - auto &ScopRIL = scop->getRequiredInvariantLoads(); - if (ScopRIL.count(dyn_cast(V))) - return; - - // Determine the ScopStmt containing the value's definition and use. There is - // no defining ScopStmt if the value is a function argument, a global value, - // or defined outside the SCoP. - Instruction *ValueInst = dyn_cast(V); - ScopStmt *ValueStmt = ValueInst ? scop->getStmtFor(ValueInst) : nullptr; - ScopStmt *UserStmt = scop->getStmtFor(UserBB); + auto *Scope = LI.getLoopFor(UserBB); + auto VUse = VirtualUse::create(scop.get(), UserStmt, Scope, V, false); + switch (VUse.getKind()) { + case VirtualUse::Constant: + case VirtualUse::Block: + case VirtualUse::Synthesizable: + case VirtualUse::Hoisted: + case VirtualUse::Intra: + // Uses of these kinds do not need a MemoryAccess. + break; + + case VirtualUse::ReadOnly: + // Add MemoryAccess for invariant values only if requested. + if (!ModelReadOnlyScalars) + break; - // We do not model uses outside the scop. - if (!UserStmt) - return; - - // Add MemoryAccess for invariant values only if requested. - if (!ModelReadOnlyScalars && !ValueStmt) - return; - - // Ignore use-def chains within the same ScopStmt. - if (ValueStmt == UserStmt) - return; + LLVM_FALLTHROUGH + case VirtualUse::Inter: - // Do not create another MemoryAccess for reloading the value if one already - // exists. - if (UserStmt->lookupValueReadOf(V)) - return; + // Do not create another MemoryAccess for reloading the value if one already + // exists. + if (UserStmt->lookupValueReadOf(V)) + break; - addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, V->getType(), true, V, - ArrayRef(), ArrayRef(), - MemoryKind::Value); - if (ValueInst) - ensureValueWrite(ValueInst); + addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, V->getType(), true, + V, ArrayRef(), ArrayRef(), + MemoryKind::Value); + + // Inter-statement uses need to write the value in their defining statement. + if (VUse.isInter()) + ensureValueWrite(cast(V)); + break; + } } void ScopBuilder::ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock, @@ -645,6 +632,76 @@ ArrayRef(), MemoryKind::PHI); } +#ifndef NDEBUG +static void verifyUse(Scop *S, Use &Op, LoopInfo &LI) { + auto PhysUse = VirtualUse::create(S, Op, &LI, false); + auto VirtUse = VirtualUse::create(S, Op, &LI, true); + assert(PhysUse.getKind() == VirtUse.getKind()); +} + +/// Check the consistency of every statement's MemoryAccesses. +/// +/// The check is carried out by expecting the "physical" kind of use (derived +/// from the BasicBlocks instructions resides in) to be same as the "virtual" +/// kind of use (derived from a statement's MemoryAccess). +/// +/// The "physical" uses are taken by ensureValueRead to determine whether to +/// create MemoryAccesses. When done, the kind of scalar access should be the +/// same no matter which way it was derived. +/// +/// The MemoryAccesses might be changed by later SCoP-modifying passes and hence +/// can intentionally influence on the kind of uses (not corresponding to the +/// "physical" anymore, hence called "virtual"). The CodeGenerator therefore has +/// to pick up the virtual uses. But here in the code generator, this has not +/// happened yet, such that virtual and physical uses are equivalent. +static void verifyUses(Scop *S, LoopInfo &LI, DominatorTree &DT) { + for (auto *BB : S->getRegion().blocks()) { + auto *Stmt = S->getStmtFor(BB); + if (!Stmt) + continue; + + for (auto &Inst : *BB) { + if (isIgnoredIntrinsic(&Inst)) + continue; + + // Branch conditions are encoded in the statement domains. + if (isa(&Inst) && Stmt->isBlockStmt()) + continue; + + // Verify all uses. + for (auto &Op : Inst.operands()) + verifyUse(S, Op, LI); + + // Stores do not produce values used by other statements. + if (isa(Inst)) + continue; + + // For every value defined in the block, also check that a use of that + // value in the same statement would not be an inter-statement use. It can + // still be synthesizable or load-hoisted, but these kind of instructions + // are not directly copied in code-generation. + auto VirtDef = + VirtualUse::create(S, Stmt, Stmt->getSurroundingLoop(), &Inst, true); + assert(VirtDef.getKind() == VirtualUse::Synthesizable || + VirtDef.getKind() == VirtualUse::Intra || + VirtDef.getKind() == VirtualUse::Hoisted); + } + } + + if (S->hasSingleExitEdge()) + return; + + // PHINodes in the SCoP region's exit block are also uses to be checked. + for (auto &Inst : *S->getRegion().getExit()) { + if (!isa(Inst)) + break; + + for (auto &Op : Inst.operands()) + verifyUse(S, Op, LI); + } +} +#endif + void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) { scop.reset(new Scop(R, SE, LI, *SD.getDetectionContext(&R))); @@ -670,6 +727,10 @@ BP->getType(), false, {AF}, {nullptr}, GlobalRead); scop->init(AA, AC, DT, LI); + +#ifndef NDEBUG + verifyUses(scop.get(), LI, DT); +#endif } ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA, Index: polly/trunk/lib/CMakeLists.txt =================================================================== --- polly/trunk/lib/CMakeLists.txt +++ polly/trunk/lib/CMakeLists.txt @@ -56,6 +56,7 @@ Support/ScopLocation.cpp Support/ISLTools.cpp Support/DumpModulePass.cpp + Support/VirtualInstruction.cpp ${POLLY_JSON_FILES} Transform/Canonicalization.cpp Transform/CodePreparation.cpp Index: polly/trunk/lib/CodeGen/BlockGenerators.cpp =================================================================== --- polly/trunk/lib/CodeGen/BlockGenerators.cpp +++ polly/trunk/lib/CodeGen/BlockGenerators.cpp @@ -22,6 +22,7 @@ #include "polly/Support/GICHelper.h" #include "polly/Support/SCEVValidator.h" #include "polly/Support/ScopHelper.h" +#include "polly/Support/VirtualInstruction.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/RegionInfo.h" #include "llvm/Analysis/ScalarEvolution.h" @@ -93,46 +94,119 @@ Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap, LoopToScevMapT <S, Loop *L) const { - // Constants that do not reference any named value can always remain - // unchanged. Handle them early to avoid expensive map lookups. We do not take - // the fast-path for external constants which are referenced through globals - // as these may need to be rewritten when distributing code accross different - // LLVM modules. - if (isa(Old) && !isa(Old)) - return Old; - - // Inline asm is like a constant to us. - if (isa(Old)) - return Old; - if (Value *New = GlobalMap.lookup(Old)) { + auto lookupGlobally = [this](Value *Old) -> Value * { + Value *New = GlobalMap.lookup(Old); + if (!New) + return nullptr; + + // Required by: + // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded.ll + // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_different_bb.ll + // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_pass_only_needed.ll + // * Isl/CodeGen/OpenMP/invariant_base_pointers_preloaded.ll + // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll + // * Isl/CodeGen/OpenMP/single_loop_with_loop_invariant_baseptr.ll + // GlobalMap should be a mapping from (value in original SCoP) to (copied + // value in generated SCoP), without intermediate mappings, which might + // easily require transitiveness as well. if (Value *NewRemapped = GlobalMap.lookup(New)) New = NewRemapped; + + // No test case for this code. if (Old->getType()->getScalarSizeInBits() < New->getType()->getScalarSizeInBits()) New = Builder.CreateTruncOrBitCast(New, Old->getType()); return New; - } - - if (Value *New = BBMap.lookup(Old)) - return New; + }; - if (Value *New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L)) - return New; - - // A scop-constant value defined by a global or a function parameter. - if (isa(Old) || isa(Old)) - return Old; - - // A scop-constant value defined by an instruction executed outside the scop. - if (const Instruction *Inst = dyn_cast(Old)) - if (!Stmt.getParent()->contains(Inst->getParent())) - return Old; - - // The scalar dependence is neither available nor SCEVCodegenable. - llvm_unreachable("Unexpected scalar dependence in region!"); - return nullptr; + Value *New = nullptr; + auto VUse = VirtualUse::create(&Stmt, L, Old, true); + switch (VUse.getKind()) { + case VirtualUse::Block: + // BasicBlock are constants, but the BlockGenerator copies them. + New = BBMap.lookup(Old); + break; + + case VirtualUse::Constant: + // Used by: + // * Isl/CodeGen/OpenMP/reference-argument-from-non-affine-region.ll + // Constants should not be redefined. In this case, the GlobalMap just + // contains a mapping to the same constant, which is unnecessary, but + // harmless. + if ((New = lookupGlobally(Old))) + break; + + assert(!BBMap.count(Old)); + New = Old; + break; + + case VirtualUse::ReadOnly: + assert(!GlobalMap.count(Old)); + + // Required for: + // * Isl/CodeGen/MemAccess/create_arrays.ll + // * Isl/CodeGen/read-only-scalars.ll + // * ScheduleOptimizer/pattern-matching-based-opts_10.ll + // For some reason these reload a read-only value. The reloaded value ends + // up in BBMap, buts its value should be identical. + // + // Required for: + // * Isl/CodeGen/OpenMP/single_loop_with_param.ll + // The parallel subfunctions need to reference the read-only value from the + // parent function, this is done by reloading them locally. + if ((New = BBMap.lookup(Old))) + break; + + New = Old; + break; + + case VirtualUse::Synthesizable: + // Used by: + // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll + // * Isl/CodeGen/OpenMP/recomputed-srem.ll + // * Isl/CodeGen/OpenMP/reference-other-bb.ll + // * Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll + // For some reason synthesizable values end up in GlobalMap. Their values + // are the same as trySynthesizeNewValue would return. The legacy + // implementation prioritized GlobalMap, so this is what we do here as well. + // Ideally, synthesizable values should not end up in GlobalMap. + if ((New = lookupGlobally(Old))) + break; + + // Required for: + // * Isl/CodeGen/RuntimeDebugBuilder/combine_different_values.ll + // * Isl/CodeGen/getNumberOfIterations.ll + // * Isl/CodeGen/non_affine_float_compare.ll + // * ScheduleOptimizer/pattern-matching-based-opts_10.ll + // Ideally, synthesizable values are synthesized by trySynthesizeNewValue, + // not precomputed (SCEVExpander has its own caching mechanism). + // These tests fail without this, but I think trySynthesizeNewValue would + // just re-synthesize the same instructions. + if ((New = BBMap.lookup(Old))) + break; + + New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L); + break; + + case VirtualUse::Hoisted: + // TODO: Hoisted invariant loads should be found in GlobalMap only, but not + // redefined locally (which will be ignored anyway). That is, the following + // assertion should apply: assert(!BBMap.count(Old)) + + New = lookupGlobally(Old); + break; + + case VirtualUse::Intra: + case VirtualUse::Inter: + assert(!GlobalMap.count(Old) && + "Intra and inter-stmt values are never global"); + New = BBMap.lookup(Old); + break; + } + assert(New && "Unexpected scalar dependence in region!"); + return New; } void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst, Index: polly/trunk/lib/Support/VirtualInstruction.cpp =================================================================== --- polly/trunk/lib/Support/VirtualInstruction.cpp +++ polly/trunk/lib/Support/VirtualInstruction.cpp @@ -0,0 +1,146 @@ +//===------ VirtualInstruction.cpp ------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Tools for determining which instructions are within a statement and the +// nature of their operands. +// +//===----------------------------------------------------------------------===// + +#include "polly/Support/VirtualInstruction.h" +#include "polly/Support/SCEVValidator.h" + +using namespace polly; +using namespace llvm; + +namespace { + +/// If InputVal is not defined in the stmt itself, return the MemoryAccess that +/// reads the scalar. Return nullptr otherwise (if the value is defined in the +/// scop, or is synthesizable) +MemoryAccess *getInputAccessOf(Value *InputVal, ScopStmt *UserStmt) { + for (auto *MA : *UserStmt) { + if (!MA->isRead()) + continue; + if (!MA->isOriginalValueKind()) + continue; + + if (MA->getAccessValue() == InputVal) + return MA; + } + return nullptr; +} +} // namespace + +VirtualUse VirtualUse ::create(Scop *S, Use &U, LoopInfo *LI, bool Virtual) { + auto *UserBB = getUseBlock(U); + auto *UserStmt = S->getStmtFor(UserBB); + auto *UserScope = LI->getLoopFor(UserBB); + return create(S, UserStmt, UserScope, U.get(), Virtual); +} + +VirtualUse VirtualUse::create(Scop *S, ScopStmt *UserStmt, Loop *UserScope, + Value *Val, bool Virtual) { + assert(!isa(Val) && "a StoreInst cannot be used"); + + if (isa(Val)) + return VirtualUse(UserStmt, Val, Block, nullptr, nullptr); + + if (isa(Val)) + return VirtualUse(UserStmt, Val, Constant, nullptr, nullptr); + + // Is the value synthesizable? If the user has been pruned + // (UserStmt == nullptr), it is either not used anywhere or is synthesizable. + // We assume synthesizable which practically should have the same effect. + auto *SE = S->getSE(); + if (SE->isSCEVable(Val->getType())) { + auto *ScevExpr = SE->getSCEVAtScope(Val, UserScope); + if (!UserStmt || canSynthesize(Val, *UserStmt->getParent(), SE, UserScope)) + return VirtualUse(UserStmt, Val, Synthesizable, ScevExpr, nullptr); + } + + // FIXME: Inconsistency between lookupInvariantEquivClass and + // getRequiredInvariantLoads. Querying one of them should be enough. + auto &RIL = S->getRequiredInvariantLoads(); + if (S->lookupInvariantEquivClass(Val) || RIL.count(dyn_cast(Val))) + return VirtualUse(UserStmt, Val, Hoisted, nullptr, nullptr); + + // ReadOnly uses may have MemoryAccesses that we want to associate with the + // use. This is why we look for a MemoryAccess here already. + MemoryAccess *InputMA = nullptr; + if (UserStmt && Virtual) + InputMA = getInputAccessOf(Val, UserStmt); + + // Uses are read-only if they have been defined before the SCoP, i.e., they + // cannot be written to inside the SCoP. Arguments are defined before any + // instructions, hence also before the SCoP. If the user has been pruned + // (UserStmt == nullptr) and is not SCEVable, assume it is read-only as it is + // neither an intra- nor an inter-use. + if (!UserStmt || isa(Val)) + return VirtualUse(UserStmt, Val, ReadOnly, nullptr, InputMA); + + auto Inst = cast(Val); + if (!S->contains(Inst)) + return VirtualUse(UserStmt, Val, ReadOnly, nullptr, InputMA); + + // A use is inter-statement if either it is defined in another statement, or + // there is a MemoryAccess that reads its value that has been written by + // another statement. + if (InputMA || (!Virtual && !UserStmt->contains(Inst->getParent()))) + return VirtualUse(UserStmt, Val, Inter, nullptr, InputMA); + + return VirtualUse(UserStmt, Val, Intra, nullptr, nullptr); +} + +void VirtualUse::print(raw_ostream &OS, bool Reproducible) const { + OS << "User: [" << User->getBaseName() << "] "; + switch (Kind) { + case VirtualUse::Constant: + OS << "Constant Op:"; + break; + case VirtualUse::Block: + OS << "BasicBlock Op:"; + break; + case VirtualUse::Synthesizable: + OS << "Synthesizable Op:"; + break; + case VirtualUse::Hoisted: + OS << "Hoisted load Op:"; + break; + case VirtualUse::ReadOnly: + OS << "Read-Only Op:"; + break; + case VirtualUse::Intra: + OS << "Intra Op:"; + break; + case VirtualUse::Inter: + OS << "Inter Op:"; + break; + } + + if (Val) { + OS << ' '; + if (Reproducible) + OS << '"' << Val->getName() << '"'; + else + Val->print(OS, true); + } + if (ScevExpr) { + OS << ' '; + ScevExpr->print(OS); + } + if (InputMA && !Reproducible) + OS << ' ' << InputMA; +} + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +void VirtualUse::dump() const { + print(errs(), false); + errs() << '\n'; +} +#endif