[CGP]Restrict complex select/phi case for optimizeMemoryInst

[skatkov]

Summary

This patch is actually a preparation for extension of the scope of optimizeMemoryInst optimization.
For now it does nothing but disable in future implementation the complex cases like
Select of Phi/Select or Phi from Select.

[john.brawn]

There's no fundamental reason why a mixture of phi and select can't be handled, but this patch probably makes more sense in the context of later patches. I'll hold off reviewing it until then.

[skatkov]

In D38533#890238, @john.brawn wrote:

There's no fundamental reason why a mixture of phi and select can't be handled, but this patch probably makes more sense in the context of later patches. I'll hold off reviewing it until then.

I tend to agree with you, right now I'm re-writing my main patch to support both Select and Phi at the same time. It seems it works. Most probably I will upload a first version of the patch tomorrow.

[skatkov]

No need for this patch. It is covered by D36073

lib/CodeGen/CodeGenPrepare.cpp

bool addNewAddrMode(ExtAddrMode &NewAddrMode) {
     }
 
     // We couldn't combine NewAddrMode with the rest, so return failure.
     AddrModes.clear();
     return false;
   }
 
   /// \brief Combine the addressing modes we've collected into a single
-  /// addressing mode.
+  /// addressing mode. OnlySingleAddrMode means that only single AddrMode
+  /// can be combined.
   /// \return True iff we successfully combined them or we only had one so
   /// didn't need to combine them anyway.
-  bool combineAddrModes() {
+  bool combineAddrModes(bool OnlySingleAddrMode) {
     // If we have no AddrModes then they can't be combined.
     if (AddrModes.size() == 0)
       return false;
 
     // A single AddrMode can trivially be combined.
     if (AddrModes.size() == 1)
       return true;
 
+    // If we cannot process other than single AddrMode, bail out now.
+    if (OnlySingleAddrMode)
+      return false;
+
     // If the AddrModes we collected are all just equal to the value they are
     // derived from then combining them wouldn't do anything useful.
     if (AllAddrModesTrivial)
       return false;
 
     // TODO: Combine multiple AddrModes by inserting a select or phi for the
     // field in which the AddrModes differ.
     return false;
bool CodeGenPrepare::optimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
   // unprofitable PRE transformations.
   SmallVector<Value*, 8> worklist;
   SmallPtrSet<Value*, 16> Visited;
   worklist.push_back(Addr);
 
   // Use a worklist to iteratively look through PHI and select nodes, and
   // ensure that the addressing mode obtained from the non-PHI/select roots of
   // the graph are compatible.
-  bool PhiOrSelectSeen = false;
+  unsigned CountPhiSeen = 0;
+  unsigned CountSelectSeen = 0;
   SmallVector<Instruction*, 16> AddrModeInsts;
   AddressingModeCombiner AddrModes;
   TypePromotionTransaction TPT(RemovedInsts);
   TypePromotionTransaction::ConstRestorationPt LastKnownGood =
       TPT.getRestorationPoint();
   while (!worklist.empty()) {
     Value *V = worklist.back();
     worklist.pop_back();
while (!worklist.empty()) {
     // as Phi. So we can safely sink address computation to memory instruction.
     if (!Visited.insert(V).second)
       continue;
 
     // For a PHI node, push all of its incoming values.
     if (PHINode *P = dyn_cast<PHINode>(V)) {
       for (Value *IncValue : P->incoming_values())
         worklist.push_back(IncValue);
-      PhiOrSelectSeen = true;
+      CountPhiSeen++;
       continue;
     }
     // Similar for select.
     if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
       worklist.push_back(SI->getFalseValue());
       worklist.push_back(SI->getTrueValue());
-      PhiOrSelectSeen = true;
+      CountSelectSeen++;
       continue;
     }
 
     // For non-PHIs, determine the addressing mode being computed.  Note that
     // the result may differ depending on what other uses our candidate
     // addressing instructions might have.
     AddrModeInsts.clear();
     ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
         V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *TRI,
         InsertedInsts, PromotedInsts, TPT);
     NewAddrMode.OriginalValue = V;
 
     if (!AddrModes.addNewAddrMode(NewAddrMode))
       break;
   }
 
+  // If we saw both selects and phis we support only one AddrMode now.
+  bool OnlySingleAddrMode = CountPhiSeen && CountSelectSeen;
+  // If we saw two selects we support only one AddrMode now.
+  if (!OnlySingleAddrMode)
+    OnlySingleAddrMode = CountSelectSeen > 1;
+
   // Try to combine the AddrModes we've collected. If we couldn't collect any,
   // or we have multiple but either couldn't combine them or combining them
   // wouldn't do anything useful, bail out now.
-  if (!AddrModes.combineAddrModes()) {
+  if (!AddrModes.combineAddrModes(OnlySingleAddrMode)) {
     TPT.rollback(LastKnownGood);
     return false;
   }
   TPT.commit();
 
   // Get the combined AddrMode (or the only AddrMode, if we only had one).
   ExtAddrMode AddrMode = AddrModes.getAddrMode();
 
   // If all the instructions matched are already in this BB, don't do anything.
   // If we saw a Phi node then it is not local definitely, and if we saw a select
   // then we want to push the address calculation past it even if it's already
   // in this BB.
-  if (!PhiOrSelectSeen && none_of(AddrModeInsts, [&](Value *V) {
+  if (!(CountPhiSeen || CountSelectSeen) &&
+      none_of(AddrModeInsts, [&](Value *V) {
         return IsNonLocalValue(V, MemoryInst->getParent());
-                  })) {
     DEBUG(dbgs() << "CGP: Found      local addrmode: " << AddrMode << "\n");
     return false;
   }
 
   // Insert this computation right after this user.  Since our caller is
   // scanning from the top of the BB to the bottom, reuse of the expr are
   // guaranteed to happen later.
   IRBuilder<> Builder(MemoryInst);

test/Transforms/CodeGenPrepare/X86/sink-addrmode.ll

entry:
   %gep1.casted = bitcast i64* %gep1 to i32*
   %base.casted = bitcast i64* %base to i32*
   %gep2 = getelementptr inbounds i32, i32* %base.casted, i64 10
   %casted.merged = select i1 %cond, i32* %gep1.casted, i32* %gep2
   %v = load i32, i32* %casted.merged, align 4
   call void @foo(i32 %v)
   ret void
 }
+
+; Make sure we can eliminate a select when both arguments perform equivalent
+; address computation. Select of Select case.
+define void @test11(i1 %cond1, i1 %cond2, i64* %base) {
+; CHECK-LABEL: @test11
+; CHECK: getelementptr i8, {{.+}} 40
+; CHECK-NOT: select
+entry:
+  %gep1 = getelementptr inbounds i64, i64* %base, i64 5
+  %gep1.casted = bitcast i64* %gep1 to i32*
+  %base.casted = bitcast i64* %base to i32*
+  %gep2 = getelementptr inbounds i32, i32* %base.casted, i64 10
+  %base2.casted = bitcast i64* %base to i8*
+  %gep3 = getelementptr inbounds i8, i8* %base2.casted, i64 40
+  %gep3.casted = bitcast i8* %gep3 to i32*
+  %casted.merged = select i1 %cond1, i32* %gep1.casted, i32* %gep2
+  %casted2.merged = select i1 %cond2, i32* %gep3.casted, i32* %casted.merged
+  %v = load i32, i32* %casted2.merged, align 4
+  call void @foo(i32 %v)
+  ret void
+}