[ConstantHoisting] Avoid hoisting constants in GEPs that index into a struct type.

[aoli]

Summary

Indices for GEPs that index into a struct type should always be
constants. This added more checks in collectConstantCandidates: which make
sure constants for GEP pointer type are not hoisted.

This fixed Bug https://bugs.llvm.org/show_bug.cgi?id=33538

[aoli]

Move headers to a proper position.

[aoli]

Update tests.

[pirama]

test/Transforms/ConstantHoisting/ARM/gep-struct-index.ll

13

Can you add a comment here clarifying that the first index into the pointer is hoisted, but the second index into the struct isn't?

[ributzka]

Why not fix AddressingModeMatcher not to crash first?

[aoli]

Update test comments.

[ributzka]

Never mind. LGTM

[aoli]

@ributzka it seems that it is guaranteed that the indices into struct type must be constants. It is not only being used by AddressingModeMatcher. It is also being used by lib/IR/Instructions.cpp:getIndexedTypeInternal. We don't want to break this guarantee so that we want to fix the constant hoisting.

[aoli]

Thank you for reviewing :)

[efriedma]

The new code here seems to overlap with llvm::canReplaceOperandWithVariable. Can we unify them?

[pirama]

In D34576#795833, @efriedma wrote:

The new code here seems to overlap with llvm::canReplaceOperandWithVariable. Can we unify them?

Unifying with canReplaceOperandWithVariable can make the code simpler. However, we'd also end up iterating the GEP once for each operand. I couldn't find any limit on the number of indices in a GEP, but would a quadratic iteration of the indices be reasonable?

[efriedma]

However, we'd also end up iterating the GEP once for each operand.

Oh, didn't think of that.

I couldn't find any limit on the number of indices in a GEP

No, there isn't a limit (although we probably have other algorithms that would explode with deeply nested types).

If we need to, we could special-case GEPs, and use canReplaceOperandWithVariable for other instructions.

[aoli]

@efriedma thank you for pointing out!

I just did some tests and I found there still some potential bugs in constant hoisting.

For insertvalue

define void @test1(%T %P) {                                                     
  %A = insertvalue %T %P, i32 256, 256                                          
  %B = insertvalue %T %P, i32 256, 256                                          
  %C = insertvalue %T %P, i32 256, 256                                          
  ret void                                                                      
}

will be optimized to

define void @test1(%T %P) {
  %const = bitcast i32 256 to i32
  %A = insertvalue %T %P, i32 %const, 256
  %B = insertvalue %T %P, i32 %const, 256
  %C = insertvalue %T %P, i32 %const, 256
  ret void
}

which is wrong (? I'm not very sure here but based on the comments in llvm::canReplaceOperandWithVariable: )

It may good for us to use llvm::canReplaceOperandWithVariable: to maintain the constancy.

[aoli]

And for quadratic iteration overhead. This function is being used in GVNSink.cpp and SimplifyCFG.cpp and there isn't any optimization for iterating the GEP. So it may okay for us also to do that?

[efriedma]

For the quadratic overhead, maybe it's just not worth worrying about; GEPs usually only have a few operands.

For your insertvalue example, I don't see any problem with that transform; the important part is that we can't transform the indexes (see http://llvm.org/docs/LangRef.html#insertvalue-instruction)

[aoli]

For your insertvalue example, I don't see any problem with that transform; the important part is that we can't transform the indexes (see http://llvm.org/docs/LangRef.html#insertvalue-instruction)

It may be a bug in canReplaceOperandWithVariable:

case Instruction::ExtractValue:
case Instruction::InsertValue:
  // All operands apart from the first are constant.
  return OpIdx == 0;

Only first operand is allowed to be set to a non-constant value.

[efriedma]

Only first operand is allowed to be set to a non-constant value.

Ah...

It's supposed to check for the first two operands for insertvalue.

[aoli]

Ah...

It's supposed to check for the first two operands for insertvalue.

Thank you for clarifying. I just want to make sure those two logic are identical.

I'll bring a new patch to fix this and unify the logic.

include/llvm/Transforms/Scalar/ConstantHoisting.h

private:
 
   Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
   SmallPtrSet<Instruction *, 8>
   findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const;
   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
                                  Instruction *Inst, unsigned Idx,
                                  ConstantInt *ConstInt);
   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
+                                 Instruction *Inst, unsigned Idx);
+  void collectConstantCandidates(ConstCandMapType &ConstCandMap,
                                  Instruction *Inst);
   void collectConstantCandidates(Function &Fn);
   void findAndMakeBaseConstant(ConstCandVecType::iterator S,
                                ConstCandVecType::iterator E);
   unsigned maximizeConstantsInRange(ConstCandVecType::iterator S,
                                     ConstCandVecType::iterator E,
                                     ConstCandVecType::iterator &MaxCostItr);
   void findBaseConstants();

lib/Transforms/Scalar/ConstantHoisting.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include <tuple>
+#include <llvm/IR/GetElementPtrTypeIterator.h>
 
 using namespace llvm;
 using namespace consthoist;
 
 #define DEBUG_TYPE "consthoist"
 
 STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
 STATISTIC(NumConstantsRebased, "Number of constants rebased");
DEBUG(if (isa<ConstantInt>(Inst->getOperand(Idx)))
           else
           dbgs() << "Collect constant " << *ConstInt << " indirectly from "
                  << *Inst << " via " << *Inst->getOperand(Idx) << " with cost "
                  << Cost << '\n';
     );
   }
 }
 
-/// \brief Scan the instruction for expensive integer constants and record them
-/// in the constant candidate vector.
-void ConstantHoistingPass::collectConstantCandidates(
-    ConstCandMapType &ConstCandMap, Instruction *Inst) {
-  // Skip all cast instructions. They are visited indirectly later on.
-  if (Inst->isCast())
-    return;
-
-  // Can't handle inline asm. Skip it.
-  if (auto Call = dyn_cast<CallInst>(Inst))
-    if (isa<InlineAsm>(Call->getCalledValue()))
-      return;
-
-  // Switch cases must remain constant, and if the value being tested is
-  // constant the entire thing should disappear.
-  if (isa<SwitchInst>(Inst))
-    return;
-
-  // Static allocas (constant size in the entry block) are handled by
-  // prologue/epilogue insertion so they're free anyway. We definitely don't
-  // want to make them non-constant.
-  auto AI = dyn_cast<AllocaInst>(Inst);
-  if (AI && AI->isStaticAlloca())
-    return;
 
-  // Scan all operands.
-  for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
-    Value *Opnd = Inst->getOperand(Idx);
+/// \brief Check the operand for instruction Inst at index Idx.
+void ConstantHoistingPass::collectConstantCandidates(
+    ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx) {
 
-    // Visit constant integers.
-    if (auto ConstInt = dyn_cast<ConstantInt>(Opnd)) {
-      collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
-      continue;
-    }
+    return;
 
-    // Visit cast instructions that have constant integers.
-    if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
-      // Only visit cast instructions, which have been skipped. All other
-      // instructions should have already been visited.
-      if (!CastInst->isCast())
-        continue;
+      return;
 
-      if (auto *ConstInt = dyn_cast<ConstantInt>(CastInst->getOperand(0))) {
-        // Pretend the constant is directly used by the instruction and ignore
-        // the cast instruction.
-        collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
-        continue;
-      }
-    }
+      return;
 
-    // Visit constant expressions that have constant integers.
-    if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
-      // Only visit constant cast expressions.
-      if (!ConstExpr->isCast())
-        continue;
+      return;
 
-      if (auto ConstInt = dyn_cast<ConstantInt>(ConstExpr->getOperand(0))) {
-        // Pretend the constant is directly used by the instruction and ignore
-        // the constant expression.
-        collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
-        continue;
+      return;
+    }
+  }
+}
+
+
+/// \brief Scan the instruction for expensive integer constants and record them
+/// in the constant candidate vector.
+void ConstantHoistingPass::collectConstantCandidates(
+    ConstCandMapType &ConstCandMap, Instruction *Inst) {
+  // Skip all cast instructions. They are visited indirectly later on.
+  if (Inst->isCast())
+    return;
+
+  // Can't handle inline asm. Skip it.
+  if (auto Call = dyn_cast<CallInst>(Inst))
+    if (isa<InlineAsm>(Call->getCalledValue()))
+      return;
+
+  // Switch cases must remain constant, and if the value being tested is
+  // constant the entire thing should disappear.
+  if (isa<SwitchInst>(Inst))
+    return;
+
+  // Static allocas (constant size in the entry block) are handled by
+  // prologue/epilogue insertion so they're free anyway. We definitely don't
+  // want to make them non-constant.
+  auto AI = dyn_cast<AllocaInst>(Inst);
+  if (AI && AI->isStaticAlloca())
+    return;
+
+  // Constants in GEPs that index into a struct type should not be hoisted.
+  if (isa<GetElementPtrInst>(Inst)) {
+    gep_type_iterator GTI = gep_type_begin(Inst);
+
+    // Collect constant for first operand.
+    collectConstantCandidates(ConstCandMap, Inst, 0);
+    // Scan rest operands.
+    for (unsigned Idx = 1, E = Inst->getNumOperands(); Idx != E; ++Idx, ++GTI) {
+      // Only collect constants that index into a non struct type.
+      if (!GTI.isStruct()) {
+        collectConstantCandidates(ConstCandMap, Inst, Idx);
       }
     }
+    return;
+  }
+
+  // Scan all operands.
+  for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
+    collectConstantCandidates(ConstCandMap, Inst, Idx);
   } // end of for all operands
 }
 
 /// \brief Collect all integer constants in the function that cannot be folded
 /// into an instruction itself.
 void ConstantHoistingPass::collectConstantCandidates(Function &Fn) {
   ConstCandMapType ConstCandMap;
   for (BasicBlock &BB : Fn)

test/Transforms/ConstantHoisting/ARM/gep-struct-index.ll

+; RUN: opt -consthoist -S < %s | FileCheck %s
+target triple = "thumbv6m-none-eabi"
+
+%T = type { i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32 }
+
+; Test if even cheap base addresses are hoisted.
+define i32 @test1(%T* %P) nounwind {
+; CHECK-LABEL:  @test1
+; CHECK:        %const = bitcast i32 256 to i32
+; CHECK:        %addr1 = getelementptr %T, %T* %P, i32 %const, i32 256
+  %addr1 = getelementptr %T, %T* %P, i32 256, i32 256
+  %tmp1 = load i32, i32* %addr1
+  %addr2 = getelementptr %T, %T* %P, i32 256, i32 256
+  %tmp2 = load i32, i32* %addr2
+  %tmp4 = add i32 %tmp1, %tmp2
+  ret i32 %tmp4
+}
+