[ValueTracking, BasicAA] Don't simplify instructions

[nikic]

Summary

GetUnderlyingObject() (and by required symmetry DecomposeGEPExpression()) will call SimplifyInstruction on the passed value if other checks fail. This simplification is very expensive, but has little effect in practice. This patch removes the SimplifyInstruction call, and replaces it with a check for single-argument phis (which can occur in canonical IR in LCSSA form), which is the only useful simplification case I was able to identify.

Compile-time numbers: http://llvm-compile-time-tracker.com/compare.php?from=be93ba1fd608cf9bef0a414c3193dff398c80c44&to=38bd3bc987b0c0f2e715859c78cd705e05689534&stat=instructions At O3 the geomean improvement is -1.7%. The largest improvement is SPASS with ThinLTO at -6%.

In test-suite, I see only two tests with a hash difference and no code size difference (PAQ8p, Ptrdist), which indicates that the simplification only ends up being useful very rarely. (I would have liked to figure out which simplification is responsible here, but wasn't able to spot it looking at transformation logs.)

[nikic]

llvm/test/CodeGen/AMDGPU/promote-alloca-to-lds-select.ll

78

Let me explain what is going on here: We have selects on undefs involved here, which means that instruction simplification will simplify to the first select operand. If a real condition is used, then that of course doesn't happen. Because of that, this test is not testing anything useful right now.

In fact, I think this indicates that the current usage of SimplifyInstruction inside GetUnderlyingObject may be subtly unsound. GetUnderlyingObject will declare that the first select operand is the underlying object, but other code is permitted to later simplify that select to the second operand instead. In this case optimizations may have been performed based on an incorrect assumption. (While undef can be true or false, it cannot be both at the same time.)

[efriedma]

LGTM

llvm/test/CodeGen/AMDGPU/promote-alloca-to-lds-select.ll

78

Makes sense. This is called out in https://github.com/llvm/llvm-project/blob/0e3faab6f0fa00668f97747a6a4afa1bc5647ef9/llvm/include/llvm/Analysis/InstructionSimplify.h#L16 .

[hfinkel]

LGTM too.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

do {
     if (Op->getOpcode() == Instruction::BitCast ||
         Op->getOpcode() == Instruction::AddrSpaceCast) {
       V = Op->getOperand(0);
       continue;
     }
 
     const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
     if (!GEPOp) {
-      if (const auto *Call = dyn_cast<CallBase>(V)) {
+      if (const auto *PHI = dyn_cast<PHINode>(V)) {
+        // Look through single-arg phi nodes created by LCSSA.
+        if (PHI->getNumIncomingValues() == 1) {
+          V = PHI->getIncomingValue(0);
+          continue;
+        }
+      } else if (const auto *Call = dyn_cast<CallBase>(V)) {
         // CaptureTracking can know about special capturing properties of some
         // intrinsics like launder.invariant.group, that can't be expressed with
         // the attributes, but have properties like returning aliasing pointer.
         // Because some analysis may assume that nocaptured pointer is not
         // returned from some special intrinsic (because function would have to
         // be marked with returns attribute), it is crucial to use this function
         // because it should be in sync with CaptureTracking. Not using it may
         // cause weird miscompilations where 2 aliasing pointers are assumed to
         // noalias.
         if (auto *RP = getArgumentAliasingToReturnedPointer(Call, false)) {
           V = RP;
           continue;
         }
       }
 
-      // If it's not a GEP, hand it off to SimplifyInstruction to see if it
-      // can come up with something. This matches what GetUnderlyingObject does.
-      if (const Instruction *I = dyn_cast<Instruction>(V))
-        // TODO: Get a DominatorTree and AssumptionCache and use them here
-        // (these are both now available in this function, but this should be
-        // updated when GetUnderlyingObject is updated). TLI should be
-        // provided also.
-        if (const Value *Simplified =
-                SimplifyInstruction(const_cast<Instruction *>(I), DL)) {
-          V = Simplified;
-          continue;
-        }
-
       Decomposed.Base = V;
       return false;
     }
 
     // Don't attempt to analyze GEPs over unsized objects.
     if (!GEPOp->getSourceElementType()->isSized()) {
       Decomposed.Base = V;
       return false;

llvm/lib/Analysis/ValueTracking.cpp

if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       V = cast<Operator>(V)->getOperand(0);
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
       if (GA->isInterposable())
         return V;
       V = GA->getAliasee();
-    } else if (isa<AllocaInst>(V)) {
-      // An alloca can't be further simplified.
-      return V;
     } else {
-      if (auto *Call = dyn_cast<CallBase>(V)) {
+      if (auto *PHI = dyn_cast<PHINode>(V)) {
+        // Look through single-arg phi nodes created by LCSSA.
+        if (PHI->getNumIncomingValues() == 1) {
+          V = PHI->getIncomingValue(0);
+          continue;
+        }
+      } else if (auto *Call = dyn_cast<CallBase>(V)) {
         // CaptureTracking can know about special capturing properties of some
         // intrinsics like launder.invariant.group, that can't be expressed with
         // the attributes, but have properties like returning aliasing pointer.
         // Because some analysis may assume that nocaptured pointer is not
         // returned from some special intrinsic (because function would have to
         // be marked with returns attribute), it is crucial to use this function
         // because it should be in sync with CaptureTracking. Not using it may
         // cause weird miscompilations where 2 aliasing pointers are assumed to
         // noalias.
         if (auto *RP = getArgumentAliasingToReturnedPointer(Call, false)) {
           V = RP;
           continue;
         }
       }
 
-      // See if InstructionSimplify knows any relevant tricks.
-      if (Instruction *I = dyn_cast<Instruction>(V))
-        // TODO: Acquire a DominatorTree and AssumptionCache and use them.
-        if (Value *Simplified = SimplifyInstruction(I, {DL, I})) {
-          V = Simplified;
-          continue;
-        }
-
       return V;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   }
   return V;
 }
 
 void llvm::GetUnderlyingObjects(const Value *V,

llvm/test/CodeGen/AMDGPU/promote-alloca-to-lds-select.ll

define amdgpu_kernel void @lds_promote_alloca_select_two_derived_constant_pointers() #0 {
   %alloca = alloca [16 x i32], align 4, addrspace(5)
   %ptr0 = getelementptr inbounds [16 x i32], [16 x i32] addrspace(5)* %alloca, i32 0, i32 1
   %ptr1 = getelementptr inbounds [16 x i32], [16 x i32] addrspace(5)* %alloca, i32 0, i32 3
   %select = select i1 undef, i32 addrspace(5)* %ptr0, i32 addrspace(5)* %ptr1
   store i32 0, i32 addrspace(5)* %select, align 4
   ret void
 }
 
+; FIXME: Can be promoted, but we'd have to recursively show that the select
+; operands all point to the same alloca.
+
 ; CHECK-LABEL: @lds_promoted_alloca_select_input_select(
-; CHECK: getelementptr inbounds [256 x [16 x i32]], [256 x [16 x i32]] addrspace(3)* @lds_promoted_alloca_select_input_select.alloca, i32 0, i32 %{{[0-9]+}}
-; CHECK: %ptr0 = getelementptr inbounds [16 x i32], [16 x i32] addrspace(3)* %{{[0-9]+}}, i32 0, i32 %a
-; CHECK: %ptr1 = getelementptr inbounds [16 x i32], [16 x i32] addrspace(3)* %{{[0-9]+}}, i32 0, i32 %b
-; CHECK: %ptr2 = getelementptr inbounds [16 x i32], [16 x i32] addrspace(3)* %{{[0-9]+}}, i32 0, i32 %c
-; CHECK: %select0 = select i1 undef, i32 addrspace(3)* %ptr0, i32 addrspace(3)* %ptr1
-; CHECK: %select1 = select i1 undef, i32 addrspace(3)* %select0, i32 addrspace(3)* %ptr2
-; CHECK: store i32 0, i32 addrspace(3)* %select1, align 4
-define amdgpu_kernel void @lds_promoted_alloca_select_input_select(i32 %a, i32 %b, i32 %c) #0 {
+; CHECK: alloca
+define amdgpu_kernel void @lds_promoted_alloca_select_input_select(i32 %a, i32 %b, i32 %c, i1 %c1, i1 %c2) #0 {
   %alloca = alloca [16 x i32], align 4, addrspace(5)
   %ptr0 = getelementptr inbounds [16 x i32], [16 x i32] addrspace(5)* %alloca, i32 0, i32 %a
   %ptr1 = getelementptr inbounds [16 x i32], [16 x i32] addrspace(5)* %alloca, i32 0, i32 %b
   %ptr2 = getelementptr inbounds [16 x i32], [16 x i32] addrspace(5)* %alloca, i32 0, i32 %c
-  %select0 = select i1 undef, i32 addrspace(5)* %ptr0, i32 addrspace(5)* %ptr1
-  %select1 = select i1 undef, i32 addrspace(5)* %select0, i32 addrspace(5)* %ptr2
+  %select0 = select i1 %c1, i32 addrspace(5)* %ptr0, i32 addrspace(5)* %ptr1
+  %select1 = select i1 %c2, i32 addrspace(5)* %select0, i32 addrspace(5)* %ptr2
   store i32 0, i32 addrspace(5)* %select1, align 4
   ret void
 }
 
 define amdgpu_kernel void @lds_promoted_alloca_select_input_phi(i32 %a, i32 %b, i32 %c) #0 {
 entry:
   %alloca = alloca [16 x i32], align 4, addrspace(5)
   %ptr0 = getelementptr inbounds [16 x i32], [16 x i32] addrspace(5)* %alloca, i32 0, i32 %a
   %ptr1 = getelementptr inbounds [16 x i32], [16 x i32] addrspace(5)* %alloca, i32 0, i32 %b
   store i32 0, i32 addrspace(5)* %ptr0
   br i1 undef, label %bb1, label %bb2