[Polly] Introduce VirtualUse. NFC.

[Meinersbur]

Summary

If a ScopStmt references a (scalar) value, there are multiple possibilities where this value can come. The decision about what kind of use it is must be handled consistently at different places, which can be error-prone. VirtualUse is meant to centralize the handling of the different types of value uses.

This patch makes ScopBuilder and CodeGeneration use VirtualUse. This already helps to show inconsistencies with the value handling. In order to keep this patch NFC, exceptions to the general rules are added. These might be fixed later if they turn to problems. Overall, this should result in fewer post-codegen IR-verification errors, but instead assertion failures in getNewValue that are closer to the actual error.

The "virtual" in VirtualUse/VirtualInstructions.h might be a misnomer as it currently has little to do with virtualizing instructions. I am open for other naming suggestions. The Virtual argument of VirtualUse::create is used to check the consistency of created MemoryAccesses, by the verifyUses function. The original intent to have Virtual in the name was that SCoP postprocessing-passes modify the accesses such that instructions are moved between ScopStmts. In order this to work, the BB an instruction resides in is less important.

For improving compile-time, caching the result of VirtualUse::create could be a possibility.

I started with using VirtualUse only for assertions. This unfortunately proved to be difficult as getNewValue as multiple returns and complete coverage.

Even if this is not committed, the study of inconsistencies of getNewValue could be useful.

[grosser]

Hi Michael,

thank you for the patch. It looks very good. I only added a couple of minor comments. Feel free to commit if you agree with them.

include/polly/Support/VirtualInstruction.h

25 ↗

(On Diff #97175)

associated WITH

40 ↗

(On Diff #97175)

double white space

81 ↗

(On Diff #97175)

"an" -> "a" MemoryAccess.

101 ↗

(On Diff #97175)

"any kind use": this sounds wrong. Do you just mean "for any use" or for "any kind of use within a statement"?

110 ↗

(On Diff #97175)

us -> is

113 ↗

(On Diff #97175)

Could you indent this?

lib/Analysis/ScopBuilder.cpp

576 ↗

(On Diff #97175)

Can you transfer the comment from the old code:

"Do not create another MemoryAccess for reloading the value if one already exists."

644 ↗

(On Diff #97175)

What is the invariant you verify here? Can you add a comment explaining it?

lib/CodeGen/BlockGenerators.cpp

136 ↗

(On Diff #97175)

IS unnecessary

185 ↗

(On Diff #97175)

Are they really pre-compute is it more that we already synthesized them once and consequently don't need to re-synthesize them again.

201 ↗

(On Diff #97175)

My guess is that we code-generate load hoisted values like all other values by copying the instruction and adding the new return value to BBMap. We likely can skip code generation for load-hoisted values. This should solve the problem. It probably does not make sense to clean this up as part of this change. So just leaving this comment and assert and fixing this later seems to be the right strategy.

209 ↗

(On Diff #97175)

Inter -> start with uppercase letter.

lib/Support/VirtualInstruction.cpp

79 ↗

(On Diff #97175)

i.e., : Comma after "i.e."

[Meinersbur]

Pre-commit update

• Spelling/grammar mistakes found by Tobias
• Doxygen comment for verifyUses
• Skip non-statement BBs entirely instead of various workarounds
• Some more/nicer comments
• Rename (Inter/Intra)Value to Inter/Intra for consistency with other enum elements
• Rename UseType to UseKind to adhere style policy http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly (and to not make clear this has nothing to do with llvm::Type)

[Meinersbur]

lib/CodeGen/BlockGenerators.cpp

185 ↗

(On Diff #97175)

This "caching" seems unintentional because it happens only in 3 test cases.

If we want to cache already synthesized values, we should let SCEVExpander do it. SCEVExpander already has a map of already synthesized values. More importantly, it also caches intermediate values and does not necessarily put them into the current BB, but also into dominating BBs such that they values can be reused in multiple BBs.

That is, SCEVExpander could do caching more efficiently. Unfortunately. we create a new SCEVExpander object (in expandCodeFor) for each value we want to synthesize, so its cache is initalized empty.

polly/trunk/include/polly/Support/VirtualInstruction.h

+//===------ 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 */

polly/trunk/lib/Analysis/ScopBuilder.cpp

 // detection derived from their LLVM-IR code.
 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/ScopBuilder.h"
 #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"
 
 using namespace llvm;
 using namespace polly;
 
 #define DEBUG_TYPE "polly-scops"
 
if (Stmt->lookupValueWriteOf(Inst))
     return;
 
   addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::MUST_WRITE, Inst,
                   Inst->getType(), true, Inst, ArrayRef<const SCEV *>(),
                   ArrayRef<const SCEV *>(), MemoryKind::Value);
 }
 
 void ScopBuilder::ensureValueRead(Value *V, BasicBlock *UserBB) {
-
-  // There cannot be an "access" for literal constants. BasicBlock references
-  // (jump destinations) also never change.
-  if ((isa<Constant>(V) && !isa<GlobalVariable>(V)) || isa<BasicBlock>(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<LoadInst>(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<Instruction>(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;
 
-  // We do not model uses outside the scop.
-  if (!UserStmt)
-    return;
-
+  case VirtualUse::ReadOnly:
     // Add MemoryAccess for invariant values only if requested.
-  if (!ModelReadOnlyScalars && !ValueStmt)
-    return;
+    if (!ModelReadOnlyScalars)
+      break;
 
-  // 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;
+      break;
 
-  addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, V->getType(), true, V,
-                  ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
+    addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, V->getType(), true,
+                    V, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                     MemoryKind::Value);
-  if (ValueInst)
-    ensureValueWrite(ValueInst);
+
+    // Inter-statement uses need to write the value in their defining statement.
+    if (VUse.isInter())
+      ensureValueWrite(cast<Instruction>(V));
+    break;
+  }
 }
 
 void ScopBuilder::ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
                                  Value *IncomingValue, bool IsExitBlock) {
   // As the incoming block might turn out to be an error statement ensure we
   // will create an exit PHI SAI object. It is needed during code generation
   // and would be created later anyway.
   if (IsExitBlock)

 }
 
 void ScopBuilder::addPHIReadAccess(PHINode *PHI) {
   addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI,
                   PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
                   ArrayRef<const SCEV *>(), 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<TerminatorInst>(&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<StoreInst>(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<PHINode>(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)));
 
   buildStmts(R);
   buildAccessFunctions(R);
 
   // In case the region does not have an exiting block we will later (during
   // code generation) split the exit block. This will move potential PHI nodes
void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
   // Create memory accesses for global reads since all arrays are now known.
   auto *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);
   for (auto *GlobalRead : GlobalReads)
     for (auto *BP : ArrayBasePointers)
       addArrayAccess(MemAccInst(GlobalRead), MemoryAccess::READ, BP,
                      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,
                          const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
                          ScopDetection &SD, ScalarEvolution &SE)
     : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE) {
 
   Function *F = R->getEntry()->getParent();

polly/trunk/lib/CMakeLists.txt

add_library(PollyCore OBJECT
   Support/GICHelper.cpp
   Support/SCEVAffinator.cpp
   Support/SCEVValidator.cpp
   Support/RegisterPasses.cpp
   Support/ScopHelper.cpp
   Support/ScopLocation.cpp
   Support/ISLTools.cpp
   Support/DumpModulePass.cpp
+  Support/VirtualInstruction.cpp
   ${POLLY_JSON_FILES}
   Transform/Canonicalization.cpp
   Transform/CodePreparation.cpp
   Transform/DeadCodeElimination.cpp
   Transform/ScheduleOptimizer.cpp
   Transform/FlattenSchedule.cpp
   Transform/FlattenAlgo.cpp
   Transform/DeLICM.cpp

polly/trunk/lib/CodeGen/BlockGenerators.cpp

 #include "polly/CodeGen/CodeGeneration.h"
 #include "polly/CodeGen/IslExprBuilder.h"
 #include "polly/CodeGen/RuntimeDebugBuilder.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #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"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "isl/aff.h"
Value *Expanded =
                     StartBlock->getSinglePredecessor());
 
   BBMap[Old] = Expanded;
   return Expanded;
 }
 
 Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
                                    LoopToScevMapT &LTS, 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<Constant>(Old) && !isa<GlobalValue>(Old))
-    return Old;
-
-  // Inline asm is like a constant to us.
-  if (isa<InlineAsm>(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;
+  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;
 
-  if (Value *New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L))
-    return New;
+  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;
 
-  // A scop-constant value defined by a global or a function parameter.
-  if (isa<GlobalValue>(Old) || isa<Argument>(Old))
-    return Old;
-
-  // A scop-constant value defined by an instruction executed outside the scop.
-  if (const Instruction *Inst = dyn_cast<Instruction>(Old))
-    if (!Stmt.getParent()->contains(Inst->getParent()))
-      return Old;
+  case VirtualUse::ReadOnly:
+    assert(!GlobalMap.count(Old));
 
-  // The scalar dependence is neither available nor SCEVCodegenable.
-  llvm_unreachable("Unexpected scalar dependence in region!");
-  return nullptr;
+    // 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,
                                     ValueMapT &BBMap, LoopToScevMapT &LTS) {
   // We do not generate debug intrinsics as we did not investigate how to
   // copy them correctly. At the current state, they just crash the code
   // generation as the meta-data operands are not correctly copied.
   if (isa<DbgInfoIntrinsic>(Inst))

polly/trunk/lib/Support/VirtualInstruction.cpp

+//===------ 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<StoreInst>(Val) && "a StoreInst cannot be used");
+
+  if (isa<BasicBlock>(Val))
+    return VirtualUse(UserStmt, Val, Block, nullptr, nullptr);
+
+  if (isa<llvm::Constant>(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<LoadInst>(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<Argument>(Val))
+    return VirtualUse(UserStmt, Val, ReadOnly, nullptr, InputMA);
+
+  auto Inst = cast<Instruction>(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