IRBuilder: Allow retrieval of the inserted instructions

[anemet]

Summary

This is an RFC.

When the Loop Vectorizer builds the instruction sequence for checks it tries
to determine the first instruction that was emitted in the current block.
This is then used to split the block.

It uses a custom solution for this implemented in the static function
getFirstInst. The pattern is something like:

Value *V = IRBuilder.CreateBlah(...);
FirstInst = getFirstInst(FirstInst, V, Loc)
Value *V2 = IRBuilder.CreateBlah(...);
FirstInst = getFirstInst(FirstInst, V2, Loc);

(Since CreateBlah may return a constant we may not generate the first
instruction for V.)

For the LoopAccessAnalysis work I need this to be made global so I was
thinking how to make it more generic. My idea was to change the approach and
rather than repeatedly checking whether we had emitted the first instruction,
remember the predecessor of the insertion point in the IRBuilder.
Subsequently, when the first emitted instruction is queried I return the
successor of the saved predecessor instruction.

Conceptually:

IRBuilder<>::Marker Mark(IRBuilder.getInsertPoint());

marks the next instruction that will be inserted at the current insertion
point. After inserting instructions into IRBuilder, you can retrieve the
first instruction inserted with Mark.get() (perhaps Mark.first() would be a
better name).

The patch also contains the changes to make use of this in LV and then asserts
that the new result is at least as good as the one from getFirstInst. The
assert does not fail on things I tried so far.

I went back and forth on this but I think it's better to associate the marker
with an insertion point rather than the IRBuilder instance itself. I had two
reasons to go this way:

1. The insertion point can be adjusted manually in the IRBuilder. This makes

it more obvious that the marker is associated with the original insertion
point after a change.

2. The behavior is more intuitive with nested IRBuilders.

For example in the LV code that I am changing we should really move the marker
earlier to also cover the SCEV expansion of the array bounds. Those
instructions are however inserted via an implicit IRBuilder inside SCEV
expansion. The good thing is that the marker as written sees these because of
the shared insertion point.

The patch is still missing unit tests but wanted to float the idea before I
get too carried away. Is this a reasonable idea? Are there other issues I am
missing?

[hfinkel]

• Original Message -----

From: "Adam Nemet" <[e-mail]>
To: [e-mail], [e-mail], [e-mail], [e-mail], [e-mail]
Cc: [e-mail]
Sent: Wednesday, February 4, 2015 5:58:45 PM
Subject: [PATCH] IRBuilder: Allow retrieval of the inserted instructions

Hi hfinkel, nadav, aschwaighofer, chandlerc,

This is an RFC.

When the Loop Vectorizer builds the instruction sequence for checks
it tries
to determine the first instruction that was emitted in the current
block.
This is then used to split the block.

Silly question: Why don't we split the block first?

-Hal

It uses a custom solution for this implemented in the static function
getFirstInst. The pattern is something like:

Value *V = IRBuilder.CreateBlah(...);
FirstInst = getFirstInst(FirstInst, V, Loc)
Value *V2 = IRBuilder.CreateBlah(...);
FirstInst = getFirstInst(FirstInst, V2, Loc);

(Since CreateBlah may return a constant we may not generate the first
instruction for V.)

For the LoopAccessAnalysis work I need this to be made global so I
was
thinking how to make it more generic. My idea was to change the
approach and
rather than repeatedly checking whether we had emitted the first
instruction,
remember the predecessor of the insertion point in the IRBuilder.
Subsequently, when the first emitted instruction is queried I return
the
successor of the saved predecessor instruction.

Conceptually:

IRBuilder<>::Marker Mark(IRBuilder.getInsertPoint());

marks the next instruction that will be inserted at the current
insertion
point. After inserting instructions into IRBuilder, you can retrieve
the
first instruction inserted with Mark.get() (perhaps Mark.first()
would be a
better name).

The patch also contains the changes to make use of this in LV and
then asserts
that the new result is at least as good as the one from getFirstInst.
The
assert does not fail on things I tried so far.

I went back and forth on this but I think it's better to associate
the marker
with an insertion point rather than the IRBuilder instance itself. I
had two
reasons to go this way:

1. The insertion point can be adjusted manually in the IRBuilder. This makes

it more obvious that the marker is associated with the original
insertion
point after a change.

2. The behavior is more intuitive with nested IRBuilders.

For example in the LV code that I am changing we should really move
the marker
earlier to also cover the SCEV expansion of the array bounds. Those
instructions are however inserted via an implicit IRBuilder inside
SCEV
expansion. The good thing is that the marker as written sees these
because of
the shared insertion point.

The patch is still missing unit tests but wanted to float the idea
before I
get too carried away. Is this a reasonable idea? Are there other
issues I am
missing?

http://reviews.llvm.org/D7421

Files:

include/llvm/IR/IRBuilder.h
lib/Transforms/Vectorize/LoopVectorize.cpp

Index: include/llvm/IR/IRBuilder.h

• include/llvm/IR/IRBuilder.h

+++ include/llvm/IR/IRBuilder.h
@@ -188,6 +188,24 @@

/// \brief Set the fast-math flags to be used with generated
fp-math operators
void SetFastMathFlags(FastMathFlags NewFMF) { FMF = NewFMF; }

+ class Marker {
+ BasicBlock::iterator Prev;
+ BasicBlock *BB;
+ public:
+ Marker(BasicBlock::iterator InsertionPoint) : BB(nullptr) {
+ if (InsertionPoint == InsertionPoint->getParent()->begin())
+ BB = InsertionPoint->getParent();
+ else
+ Prev = std::prev(InsertionPoint);
+ }
+ BasicBlock::iterator get() const {
+ if (BB)
+ return BB->begin();
+ else
+ return std::next(Prev);
+ }
+ };
+

//===--------------------------------------------------------------------===//
// RAII helpers.
//===--------------------------------------------------------------------===//

Index: lib/Transforms/Vectorize/LoopVectorize.cpp

• lib/Transforms/Vectorize/LoopVectorize.cpp

+++ lib/Transforms/Vectorize/LoopVectorize.cpp
@@ -2050,6 +2050,8 @@

}
 
IRBuilder<> ChkBuilder(Loc);

+ IRBuilder<>::Marker BeforeInsertionMarker(Loc);
+

// Our instructions might fold to a constant.
Value *MemoryRuntimeCheck = nullptr;
for (unsigned i = 0; i < NumPointers; ++i) {

@@ -2102,6 +2104,14 @@

                                               ConstantInt::getTrue(Ctx));
ChkBuilder.Insert(Check, "memcheck.conflict");
FirstInst = getFirstInst(FirstInst, Check, Loc);

+
+ Instruction *AnotherFirst = BeforeInsertionMarker.get();
+ assert(std::find_if(BasicBlock::iterator(AnotherFirst),
+ Loc->getParent()->end(),
+ [&](Instruction &I) {
+ return &I == FirstInst;
+ }) != Loc->getParent()->end());
+

return std::make_pair(FirstInst, Check);

}

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

[anemet]

I don't want to pursue this for the limited use case so remove it from the reviewers' lists.

include/llvm/IR/IRBuilder.h

public:
   void clearFastMathFlags() { FMF.clear(); }
 
   /// \brief Set the floating point math metadata to be used.
   void SetDefaultFPMathTag(MDNode *FPMathTag) { DefaultFPMathTag = FPMathTag; }
 
   /// \brief Set the fast-math flags to be used with generated fp-math operators
   void SetFastMathFlags(FastMathFlags NewFMF) { FMF = NewFMF; }
 
+  class Marker {
+    BasicBlock::iterator Prev;
+    BasicBlock *BB;
+  public:
+    Marker(BasicBlock::iterator InsertionPoint) : BB(nullptr) {
+      if (InsertionPoint == InsertionPoint->getParent()->begin())
+        BB = InsertionPoint->getParent();
+      else
+        Prev = std::prev(InsertionPoint);
+    }
+    BasicBlock::iterator get() const {
+      if (BB)
+        return BB->begin();
+      else
+        return std::next(Prev);
+    }
+  };
+
   //===--------------------------------------------------------------------===//
   // RAII helpers.
   //===--------------------------------------------------------------------===//
 
   // \brief RAII object that stores the current insertion point and restores it
   // when the object is destroyed. This includes the debug location.
   class InsertPointGuard {
     IRBuilderBase &Builder;

lib/Transforms/Vectorize/LoopVectorize.cpp

if (SE->isLoopInvariant(Sc, OrigLoop)) {
       Value *Start = Exp.expandCodeFor(PtrRtCheck->Starts[i], PtrArithTy, Loc);
       Value *End = Exp.expandCodeFor(PtrRtCheck->Ends[i], PtrArithTy, Loc);
       Starts.push_back(Start);
       Ends.push_back(End);
     }
   }
 
   IRBuilder<> ChkBuilder(Loc);
+  IRBuilder<>::Marker BeforeInsertionMarker(Loc);
+
   // Our instructions might fold to a constant.
   Value *MemoryRuntimeCheck = nullptr;
   for (unsigned i = 0; i < NumPointers; ++i) {
     for (unsigned j = i+1; j < NumPointers; ++j) {
       // No need to check if two readonly pointers intersect.
       if (!PtrRtCheck->IsWritePtr[i] && !PtrRtCheck->IsWritePtr[j])
         continue;
 
InnerLoopVectorizer::addRuntimeCheck(Instruction *Loc) {
 
   // We have to do this trickery because the IRBuilder might fold the check to a
   // constant expression in which case there is no Instruction anchored in a
   // the block.
   Instruction *Check = BinaryOperator::CreateAnd(MemoryRuntimeCheck,
                                                  ConstantInt::getTrue(Ctx));
   ChkBuilder.Insert(Check, "memcheck.conflict");
   FirstInst = getFirstInst(FirstInst, Check, Loc);
+
+  Instruction *AnotherFirst = BeforeInsertionMarker.get();
+  assert(std::find_if(BasicBlock::iterator(AnotherFirst),
+                      Loc->getParent()->end(),
+                      [&](Instruction &I) {
+                        return &I == FirstInst;
+                      }) !=  Loc->getParent()->end());
+
   return std::make_pair(FirstInst, Check);
 }
 
 void InnerLoopVectorizer::createEmptyLoop() {
   /*
    In this function we generate a new loop. The new loop will contain
    the vectorized instructions while the old loop will continue to run the
    scalar remainder.