[TypePromotionPass] Don't treat phi's as ToPromote

[dmgreen]

Summary

This attempts to stop the type promotion pass transforming where it is not profitable, by not marking PhiNodes as ToPromote.

[samparker]

It's not clear to me, from the tests, why a phi shouldn't be considered profitable... having cmp w*, w*, uxt* in those atomic loops look slower to me. Maybe we should be checking whether the phi is in a loop or not?

[dmgreen]

The goal was to fix llvm/test/CodeGen/AArch64/typepromotion-cost.ll (or a larger version of it), where there is no loop here but I believe the larger version is part of a larger loop. The point is that PhiNodes should not be considered "ToPromote" in the current cost calculation. They don't benefit from being promoted on their own - it is the uses of them that benefit.

The atomic loops are only expected to be executed once most of the time.

[samparker]

The atomic loops are only expected to be executed once most of the time.

A load compare loop is going to occur more often that just atomic operations though, such as a basic search loop. I was surprised that this didn't come up in the TypePromotion tests, so I have added some.

[samparker]

Maybe we should be checking whether the phi is in a loop or not?

And to clarify, I mean loop header phis.

[dmgreen]

In D133203#3769617, @samparker wrote:

The atomic loops are only expected to be executed once most of the time.

A load compare loop is going to occur more often that just atomic operations though, such as a basic search loop. I was surprised that this didn't come up in the TypePromotion tests, so I have added some.

OK. Hmm. Those tests don't seem to be effected by this patch. I presume they were meant to be? I've added some other tests that were.

I've been trying to think what to do about it. Best I have so far is to check if there are sinks inside the loops with sources outside. That way we are (potentially) pushing more extends out of the loop, in a way that ISel will do better with.

[samparker]

I presume they were meant to be? I've added some other tests that were.

Oh, well... thanks!

Best I have so far is to check if there are sinks inside the loops with sources outside.

Makes sense to me, and looks like it's doing the job.

LGTM.

llvm/lib/CodeGen/TypePromotion.cpp

class TypePromotion : public FunctionPass {
   // Can V have its integer type promoted, or can the type be ignored.
   bool isSupportedType(Value *V);
   // Is V an instruction with a supported opcode or another value that we can
   // handle, such as constants and basic blocks.
   bool isSupportedValue(Value *V);
   // Is V an instruction thats result can trivially promoted, or has safe
   // wrapping.
   bool isLegalToPromote(Value *V);
-  bool TryToPromote(Value *V, unsigned PromotedWidth);
+  bool TryToPromote(Value *V, unsigned PromotedWidth, const LoopInfo &LI);
 
 public:
   static char ID;
 
   TypePromotion() : FunctionPass(ID) {}
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<LoopInfoWrapperPass>();
bool TypePromotion::isLegalToPromote(Value *V) {
 
   if (isPromotedResultSafe(I) || isSafeWrap(I)) {
     SafeToPromote.insert(I);
     return true;
   }
   return false;
 }
 
-bool TypePromotion::TryToPromote(Value *V, unsigned PromotedWidth) {
+bool TypePromotion::TryToPromote(Value *V, unsigned PromotedWidth,
+                                 const LoopInfo &LI) {
   Type *OrigTy = V->getType();
   TypeSize = OrigTy->getPrimitiveSizeInBits().getFixedSize();
   SafeToPromote.clear();
   SafeWrap.clear();
 
   if (!isSupportedValue(V) || !shouldPromote(V) || !isLegalToPromote(V))
     return false;
 
bool TypePromotion::TryToPromote(Value *V, unsigned PromotedWidth,
   LLVM_DEBUG({
     dbgs() << "IR Promotion: Visited nodes:\n";
     for (auto *I : CurrentVisited)
       I->dump();
   });
 
   unsigned ToPromote = 0;
   unsigned NonFreeArgs = 0;
+  unsigned NonLoopSources = 0, LoopSinks = 0;
   SmallPtrSet<BasicBlock *, 4> Blocks;
   for (auto *CV : CurrentVisited) {
     if (auto *I = dyn_cast<Instruction>(CV))
       Blocks.insert(I->getParent());
 
     if (Sources.count(CV)) {
       if (auto *Arg = dyn_cast<Argument>(CV))
         if (!Arg->hasZExtAttr() && !Arg->hasSExtAttr())
           ++NonFreeArgs;
+      if (!isa<Instruction>(CV) ||
+          !LI.getLoopFor(cast<Instruction>(CV)->getParent()))
+        ++NonLoopSources;
       continue;
     }
 
+    if (isa<PHINode>(CV))
+      continue;
+    if (LI.getLoopFor(cast<Instruction>(CV)->getParent()))
+      ++LoopSinks;
     if (Sinks.count(cast<Instruction>(CV)))
       continue;
     ++ToPromote;
   }
 
   // DAG optimizations should be able to handle these cases better, especially
   // for function arguments.
-  if (!isa<PHINode>(V) && (ToPromote < 2 || (Blocks.size() == 1 &&
-                                             (NonFreeArgs > SafeWrap.size()))))
+  if (!isa<PHINode>(V) && !(LoopSinks && NonLoopSources) &&
+      (ToPromote < 2 || (Blocks.size() == 1 && NonFreeArgs > SafeWrap.size())))
     return false;
 
   IRPromoter Promoter(*Ctx, PromotedWidth, CurrentVisited, Sources, Sinks,
                       SafeWrap, InstsToRemove);
   Promoter.Mutate();
   return true;
 }
 
for (Instruction &I : BB) {
         EVT ZExtVT = TLI->getValueType(DL, I.getType());
         Instruction *Phi = static_cast<Instruction *>(I.getOperand(0));
         auto PromoteWidth = ZExtVT.getFixedSizeInBits();
         if (RegisterBitWidth < PromoteWidth) {
           LLVM_DEBUG(dbgs() << "IR Promotion: Couldn't find target "
                             << "register for ZExt type\n");
           continue;
         }
-        MadeChange |= TryToPromote(Phi, PromoteWidth);
+        MadeChange |= TryToPromote(Phi, PromoteWidth, LI);
       } else if (auto *ICmp = dyn_cast<ICmpInst>(&I)) {
         // Search up from icmps to try to promote their operands.
         // Skip signed or pointer compares
         if (ICmp->isSigned())
           continue;
 
         LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: " << *ICmp << "\n");
 
         for (auto &Op : ICmp->operands()) {
           if (auto *OpI = dyn_cast<Instruction>(Op)) {
             if (auto PromotedWidth = GetPromoteWidth(OpI)) {
-              MadeChange |= TryToPromote(OpI, PromotedWidth);
+              MadeChange |= TryToPromote(OpI, PromotedWidth, LI);
               break;
             }
           }
         }
       }
     }
     if (!InstsToRemove.empty()) {
       for (auto *I : InstsToRemove)

llvm/test/CodeGen/AArch64/typepromotion-cost.ll

 ; CHECK-O2-NEXT:  // %bb.1: // %lor.rhs
 ; CHECK-O2-NEXT:    cbz x1, .LBB0_5
 ; CHECK-O2-NEXT:  // %bb.2:
 ; CHECK-O2-NEXT:    mov w9, #2
 ; CHECK-O2-NEXT:    b .LBB0_4
 ; CHECK-O2-NEXT:  .LBB0_3:
 ; CHECK-O2-NEXT:    mov w9, #1
 ; CHECK-O2-NEXT:  .LBB0_4: // %lor.end.sink.split
-; CHECK-O2-NEXT:    and w8, w8, #0xffff
 ; CHECK-O2-NEXT:    cmp w8, w9
 ; CHECK-O2-NEXT:    cset w0, eq
 ; CHECK-O2-NEXT:    ret
 ; CHECK-O2-NEXT:  .LBB0_5:
 ; CHECK-O2-NEXT:    mov w0, wzr
 ; CHECK-O2-NEXT:    ret
 ;
 ; CHECK-O3-LABEL: needless_promotion:
 ; CHECK-O3:       // %bb.0: // %entry
 ; CHECK-O3-NEXT:    ldrsh w8, [x0, #4]
 ; CHECK-O3-NEXT:    tbnz w8, #31, .LBB0_3
 ; CHECK-O3-NEXT:  // %bb.1: // %lor.rhs
 ; CHECK-O3-NEXT:    cbz x1, .LBB0_4
 ; CHECK-O3-NEXT:  // %bb.2:
 ; CHECK-O3-NEXT:    mov w9, #2
-; CHECK-O3-NEXT:    and w8, w8, #0xffff
 ; CHECK-O3-NEXT:    cmp w8, w9
 ; CHECK-O3-NEXT:    cset w0, eq
 ; CHECK-O3-NEXT:    ret
 ; CHECK-O3-NEXT:  .LBB0_3:
 ; CHECK-O3-NEXT:    mov w9, #1
-; CHECK-O3-NEXT:    and w8, w8, #0xffff
 ; CHECK-O3-NEXT:    cmp w8, w9
 ; CHECK-O3-NEXT:    cset w0, eq
 ; CHECK-O3-NEXT:    ret
 ; CHECK-O3-NEXT:  .LBB0_4:
 ; CHECK-O3-NEXT:    mov w0, wzr
 ; CHECK-O3-NEXT:    ret
 entry:
   %ident = getelementptr inbounds %struct.S, ptr %S, i64 0, i32 1

 lor.end:                                          ; preds = %lor.end.sink.split, %lor.rhs
   %.shrunk = phi i32 [ 0, %lor.rhs ], [ %phi.cast, %lor.end.sink.split ]
   ret i32 %.shrunk
 }
 
 define i8 @loopcmp(ptr nocapture noundef readonly %x, i8 noundef %y) {
 ; CHECK-O2-LABEL: loopcmp:
 ; CHECK-O2:       // %bb.0: // %entry
+; CHECK-O2-NEXT:    and w9, w1, #0xff
 ; CHECK-O2-NEXT:  .LBB1_1: // %while.cond
 ; CHECK-O2-NEXT:    // =>This Inner Loop Header: Depth=1
 ; CHECK-O2-NEXT:    ldrb w8, [x0], #1
-; CHECK-O2-NEXT:    cmp w8, w1, uxtb
+; CHECK-O2-NEXT:    cmp w8, w9
 ; CHECK-O2-NEXT:    b.lo .LBB1_1
 ; CHECK-O2-NEXT:  // %bb.2: // %while.end
 ; CHECK-O2-NEXT:    mov w0, w8
 ; CHECK-O2-NEXT:    ret
 ;
 ; CHECK-O3-LABEL: loopcmp:
 ; CHECK-O3:       // %bb.0: // %entry
 ; CHECK-O3-NEXT:    and w9, w1, #0xff