Changeset View
Changeset View
Standalone View
Standalone View
llvm/lib/Target/X86/X86InstrInfo.cpp
- This file is larger than 256 KB, so syntax highlighting is disabled by default.
| Show First 20 Lines • Show All 4,013 Lines • ▼ Show 20 Lines | case X86::TEST64rr: | ||||
| return true; | return true; | ||||
| } | } | ||||
| return false; | return false; | ||||
| } | } | ||||
| bool X86InstrInfo::isRedundantFlagInstr(const MachineInstr &FlagI, | bool X86InstrInfo::isRedundantFlagInstr(const MachineInstr &FlagI, | ||||
| Register SrcReg, Register SrcReg2, | Register SrcReg, Register SrcReg2, | ||||
| int64_t ImmMask, int64_t ImmValue, | int64_t ImmMask, int64_t ImmValue, | ||||
| const MachineInstr &OI, | const MachineInstr &OI, bool *IsSwapped, | ||||
| bool *IsSwapped) const { | int64_t *ImmDelta) const { | ||||
| switch (OI.getOpcode()) { | switch (OI.getOpcode()) { | ||||
| case X86::CMP64rr: | case X86::CMP64rr: | ||||
| case X86::CMP32rr: | case X86::CMP32rr: | ||||
| case X86::CMP16rr: | case X86::CMP16rr: | ||||
| case X86::CMP8rr: | case X86::CMP8rr: | ||||
| case X86::SUB64rr: | case X86::SUB64rr: | ||||
| case X86::SUB32rr: | case X86::SUB32rr: | ||||
| case X86::SUB16rr: | case X86::SUB16rr: | ||||
| Show All 34 Lines | bool X86InstrInfo::isRedundantFlagInstr(const MachineInstr &FlagI, | ||||
| case X86::TEST16rr: | case X86::TEST16rr: | ||||
| case X86::TEST8rr: { | case X86::TEST8rr: { | ||||
| if (ImmMask != 0) { | if (ImmMask != 0) { | ||||
| Register OISrcReg; | Register OISrcReg; | ||||
| Register OISrcReg2; | Register OISrcReg2; | ||||
| int64_t OIMask; | int64_t OIMask; | ||||
| int64_t OIValue; | int64_t OIValue; | ||||
| if (analyzeCompare(OI, OISrcReg, OISrcReg2, OIMask, OIValue) && | if (analyzeCompare(OI, OISrcReg, OISrcReg2, OIMask, OIValue) && | ||||
| SrcReg == OISrcReg && ImmMask == OIMask && OIValue == ImmValue) { | SrcReg == OISrcReg && ImmMask == OIMask) { | ||||
| assert(SrcReg2 == X86::NoRegister && OISrcReg2 == X86::NoRegister && | if (OIValue == ImmValue) { | ||||
| "should not have 2nd register"); | *ImmDelta = 0; | ||||
| return true; | |||||
| } else if (static_cast<uint64_t>(ImmValue) == | |||||
| static_cast<uint64_t>(OIValue) - 1) { | |||||
| *ImmDelta = -1; | |||||
| return true; | |||||
| } else if (static_cast<uint64_t>(ImmValue) == | |||||
| static_cast<uint64_t>(OIValue) + 1) { | |||||
| *ImmDelta = 1; | |||||
| return true; | return true; | ||||
| } else { | |||||
| return false; | |||||
| } | |||||
| } | } | ||||
| } | } | ||||
| return FlagI.isIdenticalTo(OI); | return FlagI.isIdenticalTo(OI); | ||||
| } | } | ||||
| default: | default: | ||||
| return false; | return false; | ||||
| } | } | ||||
| } | } | ||||
| ▲ Show 20 Lines • Show All 227 Lines • ▼ Show 20 Lines | bool X86InstrInfo::optimizeCompareInstr(MachineInstr &CmpInstr, Register SrcReg, | ||||
| MachineInstr *MI = nullptr; | MachineInstr *MI = nullptr; | ||||
| MachineInstr *Sub = nullptr; | MachineInstr *Sub = nullptr; | ||||
| MachineInstr *Movr0Inst = nullptr; | MachineInstr *Movr0Inst = nullptr; | ||||
| bool NoSignFlag = false; | bool NoSignFlag = false; | ||||
| bool ClearsOverflowFlag = false; | bool ClearsOverflowFlag = false; | ||||
| bool ShouldUpdateCC = false; | bool ShouldUpdateCC = false; | ||||
| bool IsSwapped = false; | bool IsSwapped = false; | ||||
| X86::CondCode NewCC = X86::COND_INVALID; | X86::CondCode NewCC = X86::COND_INVALID; | ||||
| int64_t ImmDelta = 0; | |||||
| // Search backward from CmpInstr for the next instruction defining EFLAGS. | // Search backward from CmpInstr for the next instruction defining EFLAGS. | ||||
| const TargetRegisterInfo *TRI = &getRegisterInfo(); | const TargetRegisterInfo *TRI = &getRegisterInfo(); | ||||
| MachineBasicBlock &CmpMBB = *CmpInstr.getParent(); | MachineBasicBlock &CmpMBB = *CmpInstr.getParent(); | ||||
| MachineBasicBlock::reverse_iterator From = | MachineBasicBlock::reverse_iterator From = | ||||
| std::next(MachineBasicBlock::reverse_iterator(CmpInstr)); | std::next(MachineBasicBlock::reverse_iterator(CmpInstr)); | ||||
| if (SrcReg2.isPhysical()) | if (SrcReg2.isPhysical()) | ||||
| return false; | return false; | ||||
| Show All 34 Lines | for (MachineInstr &Inst : make_range(From, MBB->rend())) { | ||||
| } | } | ||||
| // Try to use EFLAGS from an instruction with similar flag results. | // Try to use EFLAGS from an instruction with similar flag results. | ||||
| // Example: | // Example: | ||||
| // sub x, y or cmp x, y | // sub x, y or cmp x, y | ||||
| // ... // EFLAGS not changed | // ... // EFLAGS not changed | ||||
| // cmp x, y // <-- can be removed | // cmp x, y // <-- can be removed | ||||
| if (isRedundantFlagInstr(CmpInstr, SrcReg, SrcReg2, CmpMask, CmpValue, | if (isRedundantFlagInstr(CmpInstr, SrcReg, SrcReg2, CmpMask, CmpValue, | ||||
| Inst, &IsSwapped)) { | Inst, &IsSwapped, &ImmDelta)) { | ||||
| Sub = &Inst; | Sub = &Inst; | ||||
| break; | break; | ||||
| } | } | ||||
| // MOV32r0 is implemented with xor which clobbers condition code. It is | // MOV32r0 is implemented with xor which clobbers condition code. It is | ||||
| // safe to move up, if the definition to EFLAGS is dead and earlier | // safe to move up, if the definition to EFLAGS is dead and earlier | ||||
| // instructions do not read or write EFLAGS. | // instructions do not read or write EFLAGS. | ||||
| if (!Movr0Inst && Inst.getOpcode() == X86::MOV32r0 && | if (!Movr0Inst && Inst.getOpcode() == X86::MOV32r0 && | ||||
| Show All 35 Lines | if (!UseEFLAGS && ModifyEFLAGS) { | ||||
| IsSafe = true; | IsSafe = true; | ||||
| break; | break; | ||||
| } | } | ||||
| if (!UseEFLAGS && !ModifyEFLAGS) | if (!UseEFLAGS && !ModifyEFLAGS) | ||||
| continue; | continue; | ||||
| // EFLAGS is used by this instruction. | // EFLAGS is used by this instruction. | ||||
| X86::CondCode OldCC = X86::COND_INVALID; | X86::CondCode OldCC = X86::COND_INVALID; | ||||
| if (MI || IsSwapped) { | if (MI || IsSwapped || ImmDelta != 0) { | ||||
| // We decode the condition code from opcode. | // We decode the condition code from opcode. | ||||
| if (Instr.isBranch()) | if (Instr.isBranch()) | ||||
| OldCC = X86::getCondFromBranch(Instr); | OldCC = X86::getCondFromBranch(Instr); | ||||
| else { | else { | ||||
| OldCC = X86::getCondFromSETCC(Instr); | OldCC = X86::getCondFromSETCC(Instr); | ||||
| if (OldCC == X86::COND_INVALID) | if (OldCC == X86::COND_INVALID) | ||||
| OldCC = X86::getCondFromCMov(Instr); | OldCC = X86::getCondFromCMov(Instr); | ||||
| } | } | ||||
| Show All 36 Lines | if (MI) { | ||||
| break; | break; | ||||
| } | } | ||||
| } else if (IsSwapped) { | } else if (IsSwapped) { | ||||
| // If we have SUB(r1, r2) and CMP(r2, r1), the condition code needs | // If we have SUB(r1, r2) and CMP(r2, r1), the condition code needs | ||||
| // to be changed from r2 > r1 to r1 < r2, from r2 < r1 to r1 > r2, etc. | // to be changed from r2 > r1 to r1 < r2, from r2 < r1 to r1 > r2, etc. | ||||
| // We swap the condition code and synthesize the new opcode. | // We swap the condition code and synthesize the new opcode. | ||||
| ReplacementCC = getSwappedCondition(OldCC); | ReplacementCC = getSwappedCondition(OldCC); | ||||
| if (ReplacementCC == X86::COND_INVALID) return false; | if (ReplacementCC == X86::COND_INVALID) return false; | ||||
| ShouldUpdateCC = true; | |||||
| } else if (ImmDelta != 0) { | |||||
| unsigned BitWidth = TRI->getRegSizeInBits(*MRI->getRegClass(SrcReg)); | |||||
| // Shift amount for min/max constants to adjust for 8/16/32 instruction | |||||
| // sizes. | |||||
| unsigned Shift = 64 - BitWidth; | |||||
| static_assert(INT64_MIN >> 32 == INT32_MIN && INT64_MIN >> 56 == INT8_MIN, | |||||
| "expected compiler with arithmetic right shift"); | |||||
foad: Surely you need `APInt::getSignedMinValue(BitWidth)`? | |||||
Good point. Changed them now. I just realized that technically this check isn't necessary as the tests I added still pass. This is because the ImmDelta calculations are actually done on int64_t values so they don't wrap around for 8/16/32 bit immediates and instead just overflow to an unrepresentable immediate. We would have overflow problems for 64bit immediates, but x86 doesn't support those. Anyway I think I'll keep the tests here anyway as I like the expressed intent, and if someone ever introduces a 64bit immediates we are prepared :) MatzeB: Good point. Changed them now.
I just realized that technically this check isn't necessary as… | |||||
| switch (OldCC) { | |||||
Is it OK to use INT64_MIN >> Shift here? I think the standard says right shift of a negative value is implementation-defined. foad: Is it OK to use `INT64_MIN >> Shift` here? I think the standard says right shift of a negative… | |||||
Good question! I think we can rely on two-complement arithmetic shift behavior here. I'm not aware of any compiler behaving differently, certainly not the one ones specified to be used for LLVM in the documentation: https://llvm.org/docs/GettingStarted.html#host-c-toolchain-both-compiler-and-standard-library Other code like APInt seems to rely on this as well: https://github.com/llvm/llvm-project/blob/4f0225f6d21b601d62b73dce913bf59d8fb93d87/llvm/include/llvm/ADT/APInt.h#L796 That said if you have a simple alternative to this, I'd be happy to change the code... MatzeB: Good question!
I think we can rely on two-complement arithmetic shift behavior here. I'm not… | |||||
How about I add this: static_assert(INT64_MIN >> 16 == INT32_MIN && INT64_MIN >> 24 == INT8_MIN,
"expects compiler with twos complement right shift");and then whoever has a whacky compiler will see the problem and can go fix it. MatzeB: How about I add this:
```
static_assert(INT64_MIN >> 16 == INT32_MIN && INT64_MIN >> 24 ==… | |||||
Not Done ReplyInline ActionsI was mostly worried a buildbot with the "undefined behaviour" sanitiser complaining about it -- though I'm not actually sure if ubsan detects this by default. I don't really mind what fix you use, if any. The static_assert sounds fine to me. Alternatively you could rewrite the expression, e.g. as ~(INT64_MAX >> Shift), but it's much less obvious what it means. foad: I was mostly worried a buildbot with the "undefined behaviour" sanitiser complaining about it… | |||||
Not Done ReplyInline ActionsWhat about using APInt? RKSimon: What about using APInt? | |||||
Seemed a bit overengineered given the value fits neatly in an uint64_t, but sure I will change it to use an APInt then. MatzeB: > What about using APInt?
Seemed a bit overengineered given the value fits neatly in an… | |||||
Or let me factor out a common helper to shift an uint64_t that we can use in APInt and here. MatzeB: Or let me factor out a common helper to shift an uint64_t that we can use in APInt and here. | |||||
| case X86::COND_L: // x <s (C + 1) --> x <=s C | |||||
| if (ImmDelta != 1 || CmpValue == INT64_MIN >> Shift) | |||||
| return false; | |||||
| ReplacementCC = X86::COND_LE; | |||||
| break; | |||||
| case X86::COND_B: // x <u (C + 1) --> x <=u C | |||||
| if (ImmDelta != 1 || CmpValue == 0) | |||||
| return false; | |||||
| ReplacementCC = X86::COND_BE; | |||||
| break; | |||||
| case X86::COND_GE: // x >=s (C + 1) --> x >s C | |||||
| if (ImmDelta != 1 || CmpValue == INT64_MIN >> Shift) | |||||
| return false; | |||||
| ReplacementCC = X86::COND_G; | |||||
| break; | |||||
| case X86::COND_AE: // x >=u (C + 1) --> x >u C | |||||
| if (ImmDelta != 1 || CmpValue == 0) | |||||
| return false; | |||||
| ReplacementCC = X86::COND_A; | |||||
| break; | |||||
| case X86::COND_G: // x >s (C - 1) --> x >=s C | |||||
| if (ImmDelta != -1 || CmpValue == INT64_MAX >> Shift) | |||||
| return false; | |||||
| ReplacementCC = X86::COND_GE; | |||||
| break; | |||||
| case X86::COND_A: // x >u (C - 1) --> x >=u C | |||||
| if (ImmDelta != -1 || | |||||
| static_cast<uint64_t>(CmpValue) == UINT64_MAX >> Shift) | |||||
| return false; | |||||
| ReplacementCC = X86::COND_AE; | |||||
| break; | |||||
| case X86::COND_LE: // x <=s (C - 1) --> x <s C | |||||
| if (ImmDelta != -1 || CmpValue == INT64_MAX >> Shift) | |||||
| return false; | |||||
| ReplacementCC = X86::COND_L; | |||||
| break; | |||||
| case X86::COND_BE: // x <=u (C - 1) --> x <u C | |||||
| if (ImmDelta != -1 || | |||||
| static_cast<uint64_t>(CmpValue) == UINT64_MAX >> Shift) | |||||
| return false; | |||||
| ReplacementCC = X86::COND_B; | |||||
| break; | |||||
| default: | |||||
| return false; | |||||
| } | |||||
| ShouldUpdateCC = true; | |||||
| } | } | ||||
| if ((ShouldUpdateCC || IsSwapped) && ReplacementCC != OldCC) { | if (ShouldUpdateCC && ReplacementCC != OldCC) { | ||||
| // Push the MachineInstr to OpsToUpdate. | // Push the MachineInstr to OpsToUpdate. | ||||
| // If it is safe to remove CmpInstr, the condition code of these | // If it is safe to remove CmpInstr, the condition code of these | ||||
| // instructions will be modified. | // instructions will be modified. | ||||
| OpsToUpdate.push_back(std::make_pair(&Instr, ReplacementCC)); | OpsToUpdate.push_back(std::make_pair(&Instr, ReplacementCC)); | ||||
| } | } | ||||
| if (ModifyEFLAGS || Instr.killsRegister(X86::EFLAGS, TRI)) { | if (ModifyEFLAGS || Instr.killsRegister(X86::EFLAGS, TRI)) { | ||||
| // It is safe to remove CmpInstr if EFLAGS is updated again or killed. | // It is safe to remove CmpInstr if EFLAGS is updated again or killed. | ||||
| IsSafe = true; | IsSafe = true; | ||||
| ▲ Show 20 Lines • Show All 4,847 Lines • Show Last 20 Lines | |||||
Surely you need APInt::getSignedMinValue(BitWidth)?