[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

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

Function addPromotedInst exactly does this.

[qcolombet]

lib/CodeGen/CodeGenPrepare.cpp

3289

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.

3301

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

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

2

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

32

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.

lib/CodeGen/CodeGenPrepare.cpp

class TypePromotionHelper {
   /// 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, ...).
   /// #2 Operand reuses:
   /// ext opnd1 to ConsideredExtType.
   /// \p PromotedInsts maps the instructions to their type before promotion.
   static bool canGetThrough(const Instruction *Inst, Type *ConsideredExtType,
                             const InstrToOrigTy &PromotedInsts, bool IsSExt);
 
   /// Utility function to determine if \p OpIdx should be promoted when
   /// promoting \p Inst.
   static bool shouldExtOperand(const Instruction *Inst, int OpIdx) {
     return !(isa<SelectInst>(Inst) && OpIdx == 0);
   }
 
   /// Utility function to promote the operand of \p Ext when this
   /// operand is a promotable trunc or sext or zext.
   /// \p PromotedInsts maps the instructions to their type before promotion.
   /// \p CreatedInstsCost[out] contains the cost of all instructions
   /// created to promote the operand of Ext.
   /// Newly added extensions are inserted in \p Exts.
   /// Newly added truncates are inserted in \p Truncs.
   /// Should never be called directly.
   /// \return The promoted value which is used instead of Ext.
   static Value *promoteOperandForTruncAndAnyExt(
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.
+  // If the instruction has conflict extension types, remove it.
+  InstrToOrigTy::iterator It = PromotedInsts.find(ExtOpnd);
+  if (It == PromotedInsts.end())
     PromotedInsts.insert(std::pair<Instruction *, TypeIsSExt>(
         ExtOpnd, TypeIsSExt(ExtOpnd->getType(), IsSExt)));
+  else if (It->second.getInt() != IsSExt)
+    PromotedInsts.erase(It);
+
   // 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");

test/Transforms/CodeGenPrepare/X86/pr38125.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
+
+; CHECK:       %promoted = trunc i32 %or to i16
+; CHECK-NEXT:  %c = sext i16 %promoted to i64
+define i32 @foo() {
+entry:
+  %cmp6 = icmp sgt i32 0, -1
+  br i1 %cmp6, label %t, label %f
+
+f:
+  br label %end
+
+t:
+  br label %end
+
+end:
+  %t3 = phi i16 [ 0, %f ], [ -3, %t ]
+  %t4 = load i16, i16* @b, align 2
+  %conv4 = zext i16 %t4 to i32
+  %or = or i16 %t3, %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
+}