[ARM] Don't convert switches to lookup tables of pointers with ROPI/RWPI

[olista01]

Summary

With the ROPI and RWPI relocation models we can't always have pointers
to global data or functions in constant data, so don't try to convert
switches into lookup tables if the type of the PHI is a pointer type. We
can still safely emit lookup tables of any non-pointer type.

[olista01]

Ping.

[efriedma]

Checking the type doesn't make sense; consider what happens if you have a PHI node with an operand i32 ptrtoint (i32* @g).

[olista01]

Check whether the value requires relocation, rather than the type.

[efriedma]

lib/Transforms/Utils/SimplifyCFG.cpp

5155

Should we be calling ValidLookupTableConstant here instead of calling shouldBuildLookupTablesForConstant directly?

[hans]

lib/Transforms/Utils/SimplifyCFG.cpp

4435

It would seem more natural to do all the target-independent checks first, and then defer to TTI for the rest.

5155

Isn't this check now already done in GetCaseResults?

[olista01]

• Remove old check of shouldBuildLookupTablesForConstant
• Re-order ValidLookupTableConstant to do target-dependent checks last

[joerg]

This change doesn't make sense to me. At most, ROPI/RWPI should enforce creation of PIC jump tables. There are some issues with the way we currently generate those, which is biting us on PPC64, but it is still the correct way forward.

[olista01]

The problem here is that this pass can create new global variables, which the backend can't recognise as jump tables (they may not actually be jump tables, as they could be tables of pointers to data).

There are a few different ways that ROPI/RWPI can be made to support pointers to globals in source code, with varying requirements on the rest of the compiler:

1. Don't do anything special, the user will have to modify their code to avoid global variables initialised to the address of a global or function. This is currently done by clang, and requires that global pointers are not introduced by LLVM.
2. Add dynamic initialisers in the frontend, called from the .init_array section. This is currently done by armclang (our clang-based bare-metal toolchain). We chose this option because it allows moving constants to a read-write section if they need dynamic initialisation, and emitting diagnostics for some C constructs that may not work properly with ROPI/RWPI. This also requires that global pointers are not introduced by LLVM.
3. Use a small dynamic loader to fix-up any global pointers. This requires linker and runtime library support, I'm not aware of any implementations of this. This wouldn't be able to fix up constants when they are loaded into ROM. This would allow the compiler to introduce global pointers, but would require them to be in a read-write section, so that their value can be adjusted by the loader.

This change supports the first two, the other option would be to modify this pass to emit all lookup tables containing pointers as variables rather than constants (and possibly modify globalopt to avoid undoing that transformation). I prefer turning off this optimisation for pointers in ROPI/RWPI modes, as it avoids embedding too much knowledge about a rather unusual ARM-specific ABI in the midend.

[olista01]

Ping

[efriedma]

lib/Transforms/Utils/SimplifyCFG.cpp

4441

I think this needs to be something more like:

if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
  if (!CE->isGEPWithNoNotionalOverIndexing())
    return false;
  if (!ValidLookupTableConstant(CE->getOperand(0)))
    return false;
}

Specifically, you need to recurse over GEPs to make sure they aren't doing anything that can't be represented in a global variable. (I guess it's an existing issue, but worth solving while you're here.)

[olista01]

lib/Transforms/Utils/SimplifyCFG.cpp

4441

Good catch, I'll put up a separate patch for that once I can find a good test for it.

[efriedma]

Okay, doing that in a separate patch is fine.

Otherwise LGTM.

include/llvm/Analysis/TargetTransformInfo.h

public:
 
   /// \brief Returns the target's jmp_buf size in bytes.
   unsigned getJumpBufSize() const;
 
   /// \brief Return true if switches should be turned into lookup tables for the
   /// target.
   bool shouldBuildLookupTables() const;
 
+  /// \brief Return true if switches should be turned into lookup tables
+  /// containing this constant value for the target.
+  bool shouldBuildLookupTablesForConstant(Constant *C) const;
+
   /// \brief Don't restrict interleaved unrolling to small loops.
   bool enableAggressiveInterleaving(bool LoopHasReductions) const;
 
   /// \brief Enable matching of interleaved access groups.
   bool enableInterleavedAccessVectorization() const;
 
   /// \brief Indicate that it is potentially unsafe to automatically vectorize
   /// floating-point operations because the semantics of vector and scalar
virtual int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
                                    int64_t Scale, unsigned AddrSpace) = 0;
   virtual bool isFoldableMemAccessOffset(Instruction *I, int64_t Offset) = 0;
   virtual bool isTruncateFree(Type *Ty1, Type *Ty2) = 0;
   virtual bool isProfitableToHoist(Instruction *I) = 0;
   virtual bool isTypeLegal(Type *Ty) = 0;
   virtual unsigned getJumpBufAlignment() = 0;
   virtual unsigned getJumpBufSize() = 0;
   virtual bool shouldBuildLookupTables() = 0;
+  virtual bool shouldBuildLookupTablesForConstant(Constant *C) = 0;
   virtual bool enableAggressiveInterleaving(bool LoopHasReductions) = 0;
   virtual bool enableInterleavedAccessVectorization() = 0;
   virtual bool isFPVectorizationPotentiallyUnsafe() = 0;
   virtual bool allowsMisalignedMemoryAccesses(LLVMContext &Context,
                                               unsigned BitWidth,
                                               unsigned AddressSpace,
                                               unsigned Alignment,
                                               bool *Fast) = 0;
bool isProfitableToHoist(Instruction *I) override {
     return Impl.isProfitableToHoist(I);
   }
   bool isTypeLegal(Type *Ty) override { return Impl.isTypeLegal(Ty); }
   unsigned getJumpBufAlignment() override { return Impl.getJumpBufAlignment(); }
   unsigned getJumpBufSize() override { return Impl.getJumpBufSize(); }
   bool shouldBuildLookupTables() override {
     return Impl.shouldBuildLookupTables();
   }
+  bool shouldBuildLookupTablesForConstant(Constant *C) override {
+    return Impl.shouldBuildLookupTablesForConstant(C);
+  }
   bool enableAggressiveInterleaving(bool LoopHasReductions) override {
     return Impl.enableAggressiveInterleaving(LoopHasReductions);
   }
   bool enableInterleavedAccessVectorization() override {
     return Impl.enableInterleavedAccessVectorization();
   }
   bool isFPVectorizationPotentiallyUnsafe() override {
     return Impl.isFPVectorizationPotentiallyUnsafe();

include/llvm/Analysis/TargetTransformInfoImpl.h

public:
 
   bool isTypeLegal(Type *Ty) { return false; }
 
   unsigned getJumpBufAlignment() { return 0; }
 
   unsigned getJumpBufSize() { return 0; }
 
   bool shouldBuildLookupTables() { return true; }
+  bool shouldBuildLookupTablesForConstant(Constant *C) { return true; }
 
   bool enableAggressiveInterleaving(bool LoopHasReductions) { return false; }
 
   bool enableInterleavedAccessVectorization() { return false; }
 
   bool isFPVectorizationPotentiallyUnsafe() { return false; }
 
   bool allowsMisalignedMemoryAccesses(LLVMContext &Context,

lib/Analysis/TargetTransformInfo.cpp

 
 unsigned TargetTransformInfo::getJumpBufSize() const {
   return TTIImpl->getJumpBufSize();
 }
 
 bool TargetTransformInfo::shouldBuildLookupTables() const {
   return TTIImpl->shouldBuildLookupTables();
 }
+bool TargetTransformInfo::shouldBuildLookupTablesForConstant(Constant *C) const {
+  return TTIImpl->shouldBuildLookupTablesForConstant(C);
+}
 
 bool TargetTransformInfo::enableAggressiveInterleaving(bool LoopHasReductions) const {
   return TTIImpl->enableAggressiveInterleaving(LoopHasReductions);
 }
 
 bool TargetTransformInfo::enableInterleavedAccessVectorization() const {
   return TTIImpl->enableInterleavedAccessVectorization();
 }

lib/Target/ARM/ARMTargetTransformInfo.h

int getArithmeticInstrCost(
       TTI::OperandValueProperties Opd2PropInfo = TTI::OP_None);
 
   int getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
                       unsigned AddressSpace);
 
   int getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy, unsigned Factor,
                                  ArrayRef<unsigned> Indices, unsigned Alignment,
                                  unsigned AddressSpace);
+
+  bool shouldBuildLookupTablesForConstant(Constant *C) const {
+    // In the ROPI and RWPI relocation models we can't have pointers to global
+    // variables or functions in constant data, so don't convert switches to
+    // lookup tables if any of the values would need relocation.
+    if (ST->isROPI() || ST->isRWPI())
+      return !C->needsRelocation();
+
+    return true;
+  }
   /// @}
 };
 
 } // end namespace llvm
 
 #endif

lib/Transforms/Utils/SimplifyCFG.cpp

for (ForwardingNodesMap::iterator I = ForwardingNodes.begin(),
     Changed = true;
   }
 
   return Changed;
 }
 
 /// Return true if the backend will be able to handle
 /// initializing an array of constants like C.
-static bool ValidLookupTableConstant(Constant *C) {
+static bool ValidLookupTableConstant(Constant *C, const TargetTransformInfo &TTI) {
   if (C->isThreadDependent())
     return false;
   if (C->isDLLImportDependent())
     return false;
 
+  if (!isa<ConstantFP>(C) && !isa<ConstantInt>(C) &&
+      !isa<ConstantPointerNull>(C) && !isa<GlobalValue>(C) &&
+      !isa<UndefValue>(C) && !isa<ConstantExpr>(C))
+    return false;
+
   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
-    return CE->isGEPWithNoNotionalOverIndexing();
+    if (!CE->isGEPWithNoNotionalOverIndexing())
+      return false;
 
-  return isa<ConstantFP>(C) || isa<ConstantInt>(C) ||
-         isa<ConstantPointerNull>(C) || isa<GlobalValue>(C) ||
-         isa<UndefValue>(C);
+  if (!TTI.shouldBuildLookupTablesForConstant(C))
+    return false;
+
+  return true;
 }
 
 /// If V is a Constant, return it. Otherwise, try to look up
 /// its constant value in ConstantPool, returning 0 if it's not there.
 static Constant *
 LookupConstant(Value *V,
                const SmallDenseMap<Value *, Constant *> &ConstantPool) {
   if (Constant *C = dyn_cast<Constant>(V))

 
 /// Try to determine the resulting constant values in phi nodes
 /// at the common destination basic block, *CommonDest, for one of the case
 /// destionations CaseDest corresponding to value CaseVal (0 for the default
 /// case), of a switch instruction SI.
 static bool
 GetCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest,
                BasicBlock **CommonDest,
-               SmallVectorImpl<std::pair<PHINode *, Constant *>> &Res,
-               const DataLayout &DL) {
+               SmallVectorImpl<std::pair<PHINode *, Constant *> > &Res,
+               const DataLayout &DL, const TargetTransformInfo &TTI) {
   // The block from which we enter the common destination.
   BasicBlock *Pred = SI->getParent();
 
   // If CaseDest is empty except for some side-effect free instructions through
   // which we can constant-propagate the CaseVal, continue to its successor.
   SmallDenseMap<Value *, Constant *> ConstantPool;
   ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
   for (BasicBlock::iterator I = CaseDest->begin(), E = CaseDest->end(); I != E;
if (Idx == -1)
       continue;
 
     Constant *ConstVal =
         LookupConstant(PHI->getIncomingValue(Idx), ConstantPool);
     if (!ConstVal)
       return false;
 
     // Be conservative about which kinds of constants we support.
-    if (!ValidLookupTableConstant(ConstVal))
+    if (!ValidLookupTableConstant(ConstVal, TTI))
       return false;
 
     Res.push_back(std::make_pair(PHI, ConstVal));
   }
 
   return Res.size() > 0;
 }
 

 // Helper function that initializes a map containing
 // results for the PHI node of the common destination block for a switch
 // instruction. Returns false if multiple PHI nodes have been found or if
 // there is not a common destination block for the switch.
 static bool InitializeUniqueCases(SwitchInst *SI, PHINode *&PHI,
                                   BasicBlock *&CommonDest,
                                   SwitchCaseResultVectorTy &UniqueResults,
                                   Constant *&DefaultResult,
-                                  const DataLayout &DL) {
+                                  const DataLayout &DL,
+                                  const TargetTransformInfo &TTI) {
   for (auto &I : SI->cases()) {
     ConstantInt *CaseVal = I.getCaseValue();
 
     // Resulting value at phi nodes for this case value.
     SwitchCaseResultsTy Results;
     if (!GetCaseResults(SI, CaseVal, I.getCaseSuccessor(), &CommonDest, Results,
-                        DL))
+                        DL, TTI))
       return false;
 
     // Only one value per case is permitted
     if (Results.size() > 1)
       return false;
     MapCaseToResult(CaseVal, UniqueResults, Results.begin()->second);
 
     // Check the PHI consistency.
     if (!PHI)
       PHI = Results[0].first;
     else if (PHI != Results[0].first)
       return false;
   }
   // Find the default result value.
   SmallVector<std::pair<PHINode *, Constant *>, 1> DefaultResults;
   BasicBlock *DefaultDest = SI->getDefaultDest();
   GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
-                 DL);
+                 DL, TTI);
   // If the default value is not found abort unless the default destination
   // is unreachable.
   DefaultResult =
       DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr;
   if ((!DefaultResult &&
        !isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg())))
     return false;
 
static void RemoveSwitchAfterSelectConversion(SwitchInst *SI, PHINode *PHI,
   }
   SI->eraseFromParent();
 }
 
 /// If the switch is only used to initialize one or more
 /// phi nodes in a common successor block with only two different
 /// constant values, replace the switch with select.
 static bool SwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder,
-                           AssumptionCache *AC, const DataLayout &DL) {
+                           AssumptionCache *AC, const DataLayout &DL,
+                           const TargetTransformInfo &TTI) {
   Value *const Cond = SI->getCondition();
   PHINode *PHI = nullptr;
   BasicBlock *CommonDest = nullptr;
   Constant *DefaultResult;
   SwitchCaseResultVectorTy UniqueResults;
   // Collect all the cases that will deliver the same value from the switch.
   if (!InitializeUniqueCases(SI, PHI, CommonDest, UniqueResults, DefaultResult,
-                             DL))
+                             DL, TTI))
     return false;
   // Selects choose between maximum two values.
   if (UniqueResults.size() != 2)
     return false;
   assert(PHI != nullptr && "PHI for value select not found");
 
   Builder.SetInsertPoint(SI);
   Value *SelectValue =
if (CaseVal->getValue().slt(MinCaseVal->getValue()))
       MinCaseVal = CaseVal;
     if (CaseVal->getValue().sgt(MaxCaseVal->getValue()))
       MaxCaseVal = CaseVal;
 
     // Resulting value at phi nodes for this case value.
     typedef SmallVector<std::pair<PHINode *, Constant *>, 4> ResultsTy;
     ResultsTy Results;
     if (!GetCaseResults(SI, CaseVal, CI.getCaseSuccessor(), &CommonDest,
-                        Results, DL))
+                        Results, DL, TTI))
       return false;
 
     // Append the result from this case to the list for each phi.
     for (const auto &I : Results) {
       PHINode *PHI = I.first;
       Constant *Value = I.second;
       if (!ResultLists.count(PHI))
         PHIs.push_back(PHI);
       ResultLists[PHI].push_back(std::make_pair(CaseVal, Value));
     }
   }
 
   // Keep track of the result types.
   for (PHINode *PHI : PHIs) {
     ResultTypes[PHI] = ResultLists[PHI][0].second->getType();
   }
 
   uint64_t NumResults = ResultLists[PHIs[0]].size();
   APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue();
   uint64_t TableSize = RangeSpread.getLimitedValue() + 1;
   bool TableHasHoles = (NumResults < TableSize);
 
   // If the table has holes, we need a constant result for the default case
   // or a bitmask that fits in a register.
   SmallVector<std::pair<PHINode *, Constant *>, 4> DefaultResultsList;
-  bool HasDefaultResults = GetCaseResults(SI, nullptr, SI->getDefaultDest(),
-                                          &CommonDest, DefaultResultsList, DL);
+  bool HasDefaultResults =
+      GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest,
+                     DefaultResultsList, DL, TTI);
 
   bool NeedMask = (TableHasHoles && !HasDefaultResults);
   if (NeedMask) {
     // As an extra penalty for the validity test we require more cases.
     if (SI->getNumCases() < 4) // FIXME: Find best threshold value (benchmark).
       return false;
     if (!DL.fitsInLegalInteger(TableSize))
       return false;
bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
   // Try to transform the switch into an icmp and a branch.
   if (TurnSwitchRangeIntoICmp(SI, Builder))
     return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
 
   // Remove unreachable cases.
   if (EliminateDeadSwitchCases(SI, AC, DL))
     return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
 
-  if (SwitchToSelect(SI, Builder, AC, DL))
+  if (SwitchToSelect(SI, Builder, AC, DL, TTI))
     return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
 
   if (ForwardSwitchConditionToPHI(SI))
     return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
 
   if (SwitchToLookupTable(SI, Builder, DL, TTI))
     return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
 

test/Transforms/SimplifyCFG/ARM/switch-to-lookup-table.ll

+; RUN: opt -S -simplifycfg -mtriple=arm -relocation-model=static    < %s | FileCheck %s --check-prefix=CHECK --check-prefix=ENABLE
+; RUN: opt -S -simplifycfg -mtriple=arm -relocation-model=pic       < %s | FileCheck %s --check-prefix=CHECK --check-prefix=ENABLE
+; RUN: opt -S -simplifycfg -mtriple=arm -relocation-model=ropi      < %s | FileCheck %s --check-prefix=CHECK --check-prefix=DISABLE
+; RUN: opt -S -simplifycfg -mtriple=arm -relocation-model=rwpi      < %s | FileCheck %s --check-prefix=CHECK --check-prefix=DISABLE
+; RUN: opt -S -simplifycfg -mtriple=arm -relocation-model=ropi-rwpi < %s | FileCheck %s --check-prefix=CHECK --check-prefix=DISABLE
+
+; CHECK:       @{{.*}} = private unnamed_addr constant [3 x i32] [i32 1234, i32 5678, i32 15532]
+; ENABLE:      @{{.*}} = private unnamed_addr constant [3 x i32*] [i32* @c1, i32* @c2, i32* @c3]
+; DISABLE-NOT: @{{.*}} = private unnamed_addr constant [3 x i32*] [i32* @c1, i32* @c2, i32* @c3]
+; ENABLE:      @{{.*}} = private unnamed_addr constant [3 x i32*] [i32* @g1, i32* @g2, i32* @g3]
+; DISABLE-NOT: @{{.*}} = private unnamed_addr constant [3 x i32*] [i32* @g1, i32* @g2, i32* @g3]
+; ENABLE:      @{{.*}} = private unnamed_addr constant [3 x i32 (i32, i32)*] [i32 (i32, i32)* @f1, i32 (i32, i32)* @f2, i32 (i32, i32)* @f3]
+; DISABLE-NOT: @{{.*}} = private unnamed_addr constant [3 x i32 (i32, i32)*] [i32 (i32, i32)* @f1, i32 (i32, i32)* @f2, i32 (i32, i32)* @f3]
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "armv7a--none-eabi"
+
+define i32 @test1(i32 %n) {
+entry:
+  switch i32 %n, label %sw.default [
+    i32 0, label %sw.bb
+    i32 1, label %sw.bb1
+    i32 2, label %sw.bb2
+  ]
+
+sw.bb:
+  br label %return
+
+sw.bb1:
+  br label %return
+
+sw.bb2:
+  br label %return
+
+sw.default:
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ 15498, %sw.default ], [ 15532, %sw.bb2 ], [ 5678, %sw.bb1 ], [ 1234, %sw.bb ]
+  ret i32 %retval.0
+}
+
+@c1 = external constant i32, align 4
+@c2 = external constant i32, align 4
+@c3 = external constant i32, align 4
+@c4 = external constant i32, align 4
+
+
+define i32* @test2(i32 %n) {
+entry:
+  switch i32 %n, label %sw.default [
+    i32 0, label %sw.bb
+    i32 1, label %sw.bb1
+    i32 2, label %sw.bb2
+  ]
+
+sw.bb:
+  br label %return
+
+sw.bb1:
+  br label %return
+
+sw.bb2:
+  br label %return
+
+sw.default:
+  br label %return
+
+return:
+  %retval.0 = phi i32* [ @c4, %sw.default ], [ @c3, %sw.bb2 ], [ @c2, %sw.bb1 ], [ @c1, %sw.bb ]
+  ret i32* %retval.0
+}
+
+@g1 = external global i32, align 4
+@g2 = external global i32, align 4
+@g3 = external global i32, align 4
+@g4 = external global i32, align 4
+
+define i32* @test3(i32 %n) {
+entry:
+  switch i32 %n, label %sw.default [
+    i32 0, label %sw.bb
+    i32 1, label %sw.bb1
+    i32 2, label %sw.bb2
+  ]
+
+sw.bb:
+  br label %return
+
+sw.bb1:
+  br label %return
+
+sw.bb2:
+  br label %return
+
+sw.default:
+  br label %return
+
+return:
+  %retval.0 = phi i32* [ @g4, %sw.default ], [ @g3, %sw.bb2 ], [ @g2, %sw.bb1 ], [ @g1, %sw.bb ]
+  ret i32* %retval.0
+}
+
+declare i32 @f1(i32, i32)
+declare i32 @f2(i32, i32)
+declare i32 @f3(i32, i32)
+declare i32 @f4(i32, i32)
+declare i32 @f5(i32, i32)
+
+define i32 @test4(i32 %a, i32 %b, i32 %c) {
+entry:
+  %cmp = icmp eq i32 %a, 1
+  br i1 %cmp, label %cond.end11, label %cond.false
+
+cond.false:
+  %cmp1 = icmp eq i32 %a, 2
+  br i1 %cmp1, label %cond.end11, label %cond.false3
+
+cond.false3:
+  %cmp4 = icmp eq i32 %a, 3
+  br i1 %cmp4, label %cond.end11, label %cond.false6
+
+cond.false6:
+  %cmp7 = icmp eq i32 %a, 4
+  %cond = select i1 %cmp7, i32 (i32, i32)* @f4, i32 (i32, i32)* @f5
+  br label %cond.end11
+
+cond.end11:
+  %cond12 = phi i32 (i32, i32)* [ @f1, %entry ], [ @f2, %cond.false ], [ %cond, %cond.false6 ], [ @f3, %cond.false3 ]
+  %call = call i32 %cond12(i32 %b, i32 %c) #2
+  ret i32 %call
+}