[CodeGenPrepare] Add BothExtension type to PromotedInsts

[Carrot]

Summary

This patch fixes PR38125.

Instruction extension types are recorded in PromotedInsts, it can be used later in function canGetThrough. If an instruction has two users with different extension types, it will be inserted into PromotedInsts two times in function promoteOperandForOther. The second one overwrites the first one, and the final extension type is wrong, later causes problem in canGetThrough.

This patch changes the simple bool extension type to 2-bit enum type, add a BothExtension type in addition to zero/sign extension. When an user sees BothExtension for an instruction, it actually knows nothing about how that instruction is extended.

[grandinj]

from someone who is just an observer: What happens when we see IsSExt types

A
B
A

?
Then the last one will re-insert A, which is probably not what you want.

[Carrot]

In D49512#1167869, @grandinj wrote:

from someone who is just an observer: What happens when we see IsSExt types

A
B
A

?
Then the last one will re-insert A, which is probably not what you want.

Good catch!
So we should record zero/sign/both extension types of an instruction instead of delete it.

[Carrot]

ping

[Carrot]

friendly ping.

[qcolombet]

Shouldn't we keep only the latest type and kind of extension?

[qcolombet]

To be more precise, the latest promotion should be correct, but if we want the full information of multiple extension, the current patch is I believe wrong.
E.g., zext (sext i8 to i16) to i32, doesn't give you the same warranties on the bit pattern than what zext i8 to i32 gives, whereas we won't be able to see that.

[qcolombet]

To be more precise, the latest promotion should be correct, but if we want the full information of multiple extension, the current patch is I believe wrong.
E.g., zext (sext i8 to i16) to i32, doesn't give you the same warranties on the bit pattern than what zext i8 to i32 gives, whereas we won't be able to see that.

[qcolombet]

lib/CodeGen/CodeGenPrepare.cpp

3600 ↗

(On Diff #156376)

Instead of insert, we should do update the value all the time.

[Carrot]

In D49512#1190372, @qcolombet wrote:

Shouldn't we keep only the latest type and kind of extension?

We should keep only the latest committed type and kind of extension, without reverted extension.

[Carrot]

In D49512#1190373, @qcolombet wrote:

To be more precise, the latest promotion should be correct, but if we want the full information of multiple extension, the current patch is I believe wrong.
E.g., zext (sext i8 to i16) to i32, doesn't give you the same warranties on the bit pattern than what zext i8 to i32 gives, whereas we won't be able to see that.

To be even more precise, the latest committed promotions should be correct, reverted promotions are not correct.

This patch does not use the full information of multiple extensions, it just marked the fact, and later query the instruction through getOrigType, BothExtension can't match any actual extension type, so nullptr is returned.

So this is a quick but conservative patch.

lib/CodeGen/CodeGenPrepare.cpp

3600 ↗

(On Diff #156376)

Function addPromotedInst exactly does this.

[qcolombet]

lib/CodeGen/CodeGenPrepare.cpp

3295 ↗

(On Diff #156376)

When the type of the extension doesn't change, we should avoid updating the type, as the source type gives more information and is still relevant.

3307 ↗

(On Diff #156376)

I missed that part on my first read. Add a comment saying that if the extension doesn't match, we cannot use the information we had on the original type.

3600 ↗

(On Diff #156376)

Oh sorry.

I missed it the first time, as I missed there was a new getOrigType function.
One thing that could help is a better documentation/name for the enum, e.g., instead of both something like stacked or instead of we saw both extension something that says one after the other.

test/Transforms/CodeGenPrepare/X86/pr38125.ll

1 ↗

(On Diff #156376)

Please use a name for the filename that conveys what this test is checking without to have to check the PR.

31 ↗

(On Diff #156376)

Can't this be simplified further?
I don't think we would need more than one block for the problem at stake, right?

[qcolombet]

Thanks for your patience.
LGTM.
One final nit below. Feel free to commit directly.

test/Transforms/CodeGenPrepare/X86/multi-extension.ll

11 ↗

(On Diff #160142)

Add a comment highlighting the characteristic of the test.
I.e., %or is reachable by both a sext and zext that are going to be promoted.

llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp

 
 static cl::opt<bool>
     EnableGEPOffsetSplit("cgp-split-large-offset-gep", cl::Hidden,
                          cl::init(true),
                          cl::desc("Enable splitting large offset of GEP."));
 
 namespace {
 
+enum ExtType {
+  ZeroExtension,   // Zero extension has been seen.
+  SignExtension,   // Sign extension has been seen.
+  BothExtension    // This extension type is used if we saw sext after
+                   // ZeroExtension had been set, or if we saw zext after
+                   // SignExtension had been set. It makes the type
+                   // information of a promoted instruction invalid.
+};
+
 using SetOfInstrs = SmallPtrSet<Instruction *, 16>;
-using TypeIsSExt = PointerIntPair<Type *, 1, bool>;
+using TypeIsSExt = PointerIntPair<Type *, 2, ExtType>;
 using InstrToOrigTy = DenseMap<Instruction *, TypeIsSExt>;
 using SExts = SmallVector<Instruction *, 16>;
 using ValueToSExts = DenseMap<Value *, SExts>;
 
 class TypePromotionTransaction;
 
   class CodeGenPrepare : public FunctionPass {
     const TargetMachine *TM = nullptr;
static bool isPromotedInstructionLegal(const TargetLowering &TLI,
   return TLI.isOperationLegalOrCustom(
       ISDOpcode, TLI.getValueType(DL, PromotedInst->getType()));
 }
 
 namespace {
 
 /// Hepler class to perform type promotion.
 class TypePromotionHelper {
+  /// Utility function to add a promoted instruction \p ExtOpnd to
+  /// \p PromotedInsts and record the type of extension we have seen.
+  static void addPromotedInst(InstrToOrigTy &PromotedInsts,
+                              Instruction *ExtOpnd,
+                              bool IsSExt) {
+    ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
+    InstrToOrigTy::iterator It = PromotedInsts.find(ExtOpnd);
+    if (It != PromotedInsts.end()) {
+      // If the new extension is same as original, the information in
+      // PromotedInsts[ExtOpnd] is still correct.
+      if (It->second.getInt() == ExtTy)
+        return;
+
+      // Now the new extension is different from old extension, we make
+      // the type information invalid by setting extension type to
+      // BothExtension.
+      ExtTy = BothExtension;
+    }
+    PromotedInsts[ExtOpnd] = TypeIsSExt(ExtOpnd->getType(), ExtTy);
+  }
+
+  /// Utility function to query the original type of instruction \p Opnd
+  /// with a matched extension type. If the extension doesn't match, we
+  /// cannot use the information we had on the original type.
+  /// BothExtension doesn't match any extension type.
+  static const Type *getOrigType(const InstrToOrigTy &PromotedInsts,
+                                 Instruction *Opnd,
+                                 bool IsSExt) {
+    ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
+    InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
+    if (It != PromotedInsts.end() && It->second.getInt() == ExtTy)
+      return It->second.getPointer();
+    return nullptr;
+  }
+
   /// Utility function to check whether or not a sign or zero extension
   /// of \p Inst with \p ConsideredExtType can be moved through \p Inst by
   /// either using the operands of \p Inst or promoting \p Inst.
   /// The type of the extension is defined by \p IsSExt.
   /// In other words, check if:
   /// ext (Ty Inst opnd1 opnd2 ... opndN) to ConsideredExtType.
   /// #1 Promotion applies:
   /// ConsideredExtType Inst (ext opnd1 to ConsideredExtType, ...).
bool TypePromotionHelper::canGetThrough(const Instruction *Inst,
   Instruction *Opnd = dyn_cast<Instruction>(OpndVal);
   if (!Opnd)
     return false;
 
   // Check if the source of the type is narrow enough.
   // I.e., check that trunc just drops extended bits of the same kind of
   // the extension.
   // #1 get the type of the operand and check the kind of the extended bits.
-  const Type *OpndType;
-  InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
-  if (It != PromotedInsts.end() && It->second.getInt() == IsSExt)
-    OpndType = It->second.getPointer();
+  const Type *OpndType = getOrigType(PromotedInsts, Opnd, IsSExt);
+  if (OpndType)
+    ;
   else if ((IsSExt && isa<SExtInst>(Opnd)) || (!IsSExt && isa<ZExtInst>(Opnd)))
     OpndType = Opnd->getOperand(0)->getType();
   else
     return false;
 
   // #2 check that the truncate just drops extended bits.
   return Inst->getType()->getIntegerBitWidth() >=
          OpndType->getIntegerBitWidth();
Value *TypePromotionHelper::promoteOperandForOther(
 
   // Get through the Instruction:
   // 1. Update its type.
   // 2. Replace the uses of Ext by Inst.
   // 3. Extend each operand that needs to be extended.
 
   // Remember the original type of the instruction before promotion.
   // This is useful to know that the high bits are sign extended bits.
-  PromotedInsts.insert(std::pair<Instruction *, TypeIsSExt>(
-      ExtOpnd, TypeIsSExt(ExtOpnd->getType(), IsSExt)));
+  addPromotedInst(PromotedInsts, ExtOpnd, IsSExt);
   // Step #1.
   TPT.mutateType(ExtOpnd, Ext->getType());
   // Step #2.
   TPT.replaceAllUsesWith(Ext, ExtOpnd);
   // Step #3.
   Instruction *ExtForOpnd = Ext;
 
   LLVM_DEBUG(dbgs() << "Propagate Ext to operands\n");

llvm/trunk/test/Transforms/CodeGenPrepare/X86/multi-extension.ll

+; RUN: opt < %s -codegenprepare -S -mtriple=x86_64-unknown-unknown    | FileCheck %s
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.13.0"
+
+declare void @bar(i64)
+
+@b = global i16 0, align 2
+
+; This test case is extracted from PR38125.
+; %or is reachable by both a sext and zext that are going to be promoted.
+; It ensures correct operation on PromotedInsts.
+
+; CHECK:       %promoted = trunc i32 %or to i16
+; CHECK-NEXT:  %c = sext i16 %promoted to i64
+define i32 @foo(i16 %kkk) {
+entry:
+  %t4 = load i16, i16* @b, align 2
+  %conv4 = zext i16 %t4 to i32
+  %or = or i16 %kkk, %t4
+  %c = sext i16 %or to i64
+  call void @bar(i64 %c)
+  %t5 = and i16 %or, 5
+  %z = zext i16 %t5 to i32
+  ret i32 %z
+}