[SystemZ] Utilize Compare/Add/Sub "High" instructions

[jonpa]

Summary

Use GRX32 Mux pseudo instructions for compare, add and sub.

Use regalloc hints and a new target hook to control copy propagation after (and during) regalloc to minimize the number of pseudos ending up with unsupported register combinations.

[jonpa]

The patch as of now is a work in progress (experimental).

Only one pseudo right now ends up being unsupported :-)

This seems generally beneficial:

Opcode counts differences. master <> patch
chlr           :                    0                 1874    +1874
ar             :                18873                19564     +691
chhr           :                    0                  617     +617
srk            :                 3742                 3252     -490
ahhlr          :                    0                  461     +461
ark            :                 4985                 4554     -431
clhlr          :                    0                  385     +385
shhlr          :                    0                  313     +313
sr             :                 6059                 6349     +290
cr             :                 4560                 4279     -281
clr            :                 1125                 1047      -78
shhhr          :                    0                   47      +47
ahhhr          :                    0                   34      +34
clhhr          :                    0                   31      +31
alr            :                    4                    3       -1
alhhlr         :                    0                    1       +1
Spill|Reload   :               189169               187154    -2015

Number of register moves instructions per benchark:
Reg moves         spec-llvm_A_master/              spec-llvm
447.dealII     :                67389                  66960     -429
454.calculix   :                19298                  19131     -167
444.namd       :                 6464                   6572     +108
435.gromacs    :                16386                  16283     -103
403.gcc        :                73292                  73204      -88
450.soplex     :                 7779                   7706      -73
483.xalancbmk  :               109978                 109932      -46
453.povray     :                15298                  15263      -35
400.perlbench  :                21702                  21731      +29
482.sphinx3    :                 3024                   3001      -23
445.gobmk      :                16052                  16030      -22
436.cactusADM  :                11225                  11235      +10
464.h264ref    :                 7998                   7988      -10
456.hmmer      :                 5741                   5734       -7
401.bzip2      :                 1161                   1155       -6
... (<= 5)
Reg moves      :               415172               414309       -863

[jonpa]

Still INCOMPLETE! SPEC builds, but this patch is still experimental.

The handling of hintRecoloring() / MachineCopyPropagation has been simplified. By using a new pass SystemZSelectMux immediately after virtregrewrite but before MCP. The selected legal instructions with High/Low register classes can not get bad registers from later passes. The Mux pseudos that did not get a legal allocation get handled as before by SystemZExpandPseudo, to let passes after regalloc, such as machine sinking optimize them.

Minispec performance measurements show some varying results.

Stats from SPEC builds:

Master (z13)
------------

Number of LOCRMux jump-sequences         :         1
Number of load-and-test instructions     :     65516
Number of Mux pseudo compares CC live out:         0

Number of spilled live ranges                 :     57661
Number of spills inserted                     :     53601
Number of copies between allocatable physregs :    412658


"Hard hints only to avoid illegal muxes" (z13)
----------------------------------------------

Number of LOCRs                          :      7649
Number of LOCRMux jump-sequences         :         9
Number of load-and-test instructions     :     65535
Number of Muxes using only low parts     :     70026
Number of Muxes using only high parts    :       704
Number of Muxes using high and low parts :      2828

Number of Muxes illegal registers        :         8
Number of Muxes neeeding copy to dst     :         3
Number of Muxes neeeding two rotates     :         0
Number of Mux pseudo compares swapped    :         5
Num Mux pseudo cmps not locally updatable:         0
Number of Mux pseudo compares CC live out:         0

Number of spilled live ranges                 :     56884
Number of spills inserted                     :     52783
Number of copies between allocatable physregs :    412981


Same, plus "Hard hints for All-high or All-low" (z13)
-----------------------------------------------------

Number of LOCRs                          :      7649
Number of LOCRMux jump-sequences         :         9
Number of load-and-test instructions     :     65536
Number of Muxes using only low parts     :     72184
Number of Muxes using only high parts    :      1352
Number of Muxes using high and low parts :        23

Number of Muxes illegal registers        :         7
Number of Muxes neeeding copy to dst     :         2
Number of Muxes neeeding two rotates     :         0
Number of Mux pseudo compares swapped    :         5
Num Mux pseudo cmps not locally updatable:         0
Number of Mux pseudo compares CC live out:         0

Number of spilled live ranges                 :     57248
Number of spills inserted                     :     53190
Number of copies between allocatable physregs :    413166


Same, but "Soft hints for All-high or All-low" (z13)
----------------------------------------------------

Number of LOCRs                          :      7649
Number of LOCRMux jump-sequences         :         9
Number of load-and-test instructions     :     65562
Number of Muxes using only low parts     :     71497
Number of Muxes using only high parts    :      1407
Number of Muxes using high and low parts :       654

Number of Muxes illegal registers        :         8
Number of Muxes neeeding copy to dst     :         3
Number of Muxes neeeding two rotates     :         0
Number of Mux pseudo compares swapped    :         5
Num Mux pseudo cmps not locally updatable:         0
Number of Mux pseudo compares CC live out:         0

Number of spilled live ranges                 :     57016
Number of spills inserted                     :     52924
Number of copies between allocatable physregs :    412950

[jonpa]

Patch is still experimental, but updated with the latest improvements.

• Fall backs implemented in SystemZExpandPseudo.cpp, using register copys, rotates, commutation, negation...
• Compare muxes not getting regalloc hints except when CC is live out, which improves things a bit. Extra CC liveness check added in SystemZExpandPseudo.

...

[jonpa]

Patch refined / improved.

[jonpa]

Regalloc hints for llc/llh added as well, which handled two regressions.

[qcolombet]

The generic changes look sensible to me.
I would just suggest to add a comment on what VRM is for on the modified methods.

lib/Target/SystemZ/SystemZRegisterInfo.cpp

316

Either make VRM a reference on the prototype, or check that it is not nullptr.
In theory a caller could pass nullptr.

[jonpa]

Thank you Quentin for the review! Patch updated per your suggestions. (I am not sure why LIS and VRM are optional parameters to foldMemoryOperandImpl(). It would have simplified my patch somewhat if they were not, but I instead added a check to see that VRM is available.)

Plus some minor fixes.

[uweigand]

Not a full review yet, but a couple of comments (in the test case) where the resulting code could be simplified.

test/CodeGen/SystemZ/expand-mux-pseudos.mir

61

This doesn't need to have a four-instruction sequence. The first two instructions simply duplicate the r2h value into both r2l and r2h; this can be done in a single risblg instruction.

137

Same as above.

148

This is a bit of a silly case since it implements X - X, so it doesn't matter what X was. This means the risblg is just dead code. (OTOH one would hope that the optimizers would have removed that already anyway ...)

156

Again a case of X - X, where the risbhg is dead.

[jonpa]

Don't build a new MI in selectAddSubMux(), but instead update the registers, MCInstrDesc and TiedTo flag. This avoids the need to update SlotIndexes. This is needed to not loose any extra ("regalloc") operands or instruction flags (such as "nsw") . Question: Are there any such flags that should be modified when commutation is performed on a sub and it becomes an add?

Some minor fixing:

• Don't pass TRI or TII to MuxInfo member functions (for readability).
• Remove confusing MuxInfo::PseudoOpcode member - might as well just set the MCInstrDesc temporarily in negateRHSIfSub().

[jonpa]

Patch refactored, with very near NFC.

• Merged SystemZSelectMux and SystemZExpandPseudo passes (the latter removed). This seems to mean that "MachineDominator Tree Construction" and "Machine Natural Loop Construction" is run one extra time (5 instead of 4 times). This is because they are not marked as preserved, since it is theoretically possible that LOCRMuxes get expanded and change CFG. Is it this ok, or is there a simple way to mark those analysises as preserved, and then only recomputing them if needed? (something like releaseMemory() + runOnMachineFunction() for both MLI and MDT, maybe?).

• MuxInfo simplified. Instead of Regs[], MachineOperands are updated directly, with hopefully correct flags.

Todo: Tests to verify that all cases are correctly handled, with correct register flags.

[jonpa]

• SystemZSelectMux.cpp merged into SystemZPostRewrite.cpp.

• Mux instructions now only 3-address, with simplified instruction classes. Instruction mappings for getTwoOperandOpcode() and getMemOpcode() added.

• foldMemoryOperandImpl() improved.

• Bugfix in MuxInfo::RotateReg0(): Only add an implicit use of the 32-bit register if it is *used* (not if it is just defined).

• getRegAllocationHints()
  • don't give 2-address hints for a GRH32 reg, since it would be useless. (This strangely seemed to increse spilling a bit at least on that day).
  • for GRX32 regs:
    • instead of iterative searches, revisit constrained regs immediately (push to front of worklist).
    • put a limit on the number of visited regs (excluding any revisits). This also influences the aggressiveness of the algorithm.
    • break out of loop over MIs if current Reg will be revisited.

On SPEC 2006, with unlimited hints search, I saw with -time-passes a very slight increase in compile time with the patch compared to master:
Average Wall Time for Greedy Register Allocator: 1.41% -> 1.42%
Average User Time for Greedy Register Allocator: 1.42% -> 1.45%

As well, it seems that the worst cases of relative compile time are not getting worse.

It seems that even with unlimited search, compile time is not an issue, so a high limit like 50 seems to be acceptable. See below for some stats with different values of "maxregs".

• Exhaustive testing in expand-mux-pseudos.mir: all combinations of low/high as well as same/different GR64 regs.

TODO:

• ThreeAddr: - Should all of the 2-address conversions be done in PostRewrite?
• Swap compare operands in foldMemoryOperandImpl()? Can we trust live-in lists for checking if CC is live-out?
• return false from allowHintRecoloring() for MemFoldPseudos to avoid the few cases of copying?
• SystemZISelLowering.cpp::reverseCCMask() merge with new code for swapping compare operands?
• SystemZPostRewrite::runOnMachineFunction() should return true even if only updateLiveInLists_CC() changed MF?
• Update CFG when expanding LOCRMUXr and give setPreservesAll()?

Before commit:

• remove some/most experimental stats.

Here is a summary of the effects of different values of -maxregs (experimental option in SystemZRegisterInfo.cpp).

• regalloc/systemz statistics as reported by the llvm option "-stats"
• "Spill|Reload" is the number of times the comment "Spill" or "Reload" is seen in .s files.
• "Copies" is the number of instructions built by copyPhysReg() seen in .s files.

This was done on SPEC 2006, but also previously on 2017, where there seems to be similar results, although it seemed like the value of maxregs=50 was
needed to not need any mux fallbacks at all (for 2006 it is maxregs=40, see below).

master
     57380                       regalloc - Number of spilled live ranges
         6                     systemz-II - Number of LOCRMux jump-sequences (lower is better)

master <> master
Spill|Reload   :               188230               188230       +0
Copies         :               423366               423366       +0

HiMuxes: maxregs=100
     56046                       regalloc - Number of spilled live ranges

master <> patch
Spill|Reload   :               188230               183270    -4960
Copies         :               423366               426449    +3083

HiMuxes: maxregs=50
     56046                       regalloc - Number of spilled live ranges

master <> patch
Spill|Reload   :               188230               183270    -4960
Copies         :               423366               426449    +3083

HiMuxes: maxregs=40
     56046                       regalloc - Number of spilled live ranges

master <> patch
Spill|Reload   :               188230               183270    -4960
Copies         :               423366               426449    +3083

HiMuxes: maxregs=30
     56030                       regalloc - Number of spilled live ranges
         9            systemz-postrewrite - Number of Mux pseudos needing a copy to dst.
         9            systemz-postrewrite - Number of Mux pseudos needing two rotates of a reg.

master <> patch
Spill|Reload   :               188230               183238    -4992
Copies         :               423366               426457    +3091

HiMuxes: maxregs=20
     56029                       regalloc - Number of spilled live ranges
         8            systemz-postrewrite - Number of Mux pseudos needing a copy to dst.
        11            systemz-postrewrite - Number of Mux pseudos needing two rotates of a reg.

master <> patch
Spill|Reload   :               188230               183236    -4994
Copies         :               423366               426456    +3090

HiMuxes: maxregs=15
     56019                       regalloc - Number of spilled live ranges
         9            systemz-postrewrite - Number of Mux pseudos needing a copy to dst.
        14            systemz-postrewrite - Number of Mux pseudos needing two rotates of a reg.

master <> patch
Spill|Reload   :               188230               183224    -5006
Copies         :               423366               426458    +3092

HiMuxes: maxregs=10
     55989                       regalloc - Number of spilled live ranges
        22            systemz-postrewrite - Number of Mux pseudos needing a copy to dst.
        43            systemz-postrewrite - Number of Mux pseudos needing two rotates of a reg.
         1            systemz-postrewrite - Number of Mux pseudos negation of RHS (subtractions).

master <> patch
Spill|Reload   :               188230               183159    -5071
Copies         :               423366               426473    +3107

HiMuxes: maxregs=5
     55988                       regalloc - Number of spilled live ranges
        27            systemz-postrewrite - Number of LOCRMux jump-sequences (lower is better)
        29            systemz-postrewrite - Number of Mux pseudos needing a copy to dst.
        63            systemz-postrewrite - Number of Mux pseudos needing two rotates of a reg.
         1            systemz-postrewrite - Number of Mux pseudos negation of RHS (subtractions).

master <> patch
Spill|Reload   :               188230               183277    -4953
Copies         :               423366               426557    +3191

Without any GRX32 hints at all:

     53931                       regalloc - Number of spilled live ranges
      1483            systemz-postrewrite - Number of LOCRMux jump-sequences (lower is better)
        49            systemz-postrewrite - Number of Mux pseudo compares with live out CC.
      3283            systemz-postrewrite - Number of Mux pseudos needing a copy to dst.
      3969            systemz-postrewrite - Number of Mux pseudos needing two rotates of a reg.
       117            systemz-postrewrite - Number of Mux pseudos negation of RHS (subtractions).

master <> patch
Spill|Reload   :               188230               180090    -8140
Copies         :               423366               431998    +8632

I also tried to use soft hints instead of hard hints to avoid fallbacks once, and it seemed to give a result somewhere in between "no GRX32 hints at all" and the patch.

[jonpa]

test/CodeGen/SystemZ/expand-mux-pseudos.mir

61

OK, I added a special handling for that case in expandAddSubMux().

148

Since this is just a MIR test anyway I would like to test all possible combinations even if they do not make much sense.

[jonpa]

Don't skip all 2-address hints in getRegallocationHints() just because it's a GRH32 register: AHIMuxK actually can expand to a 2-address instruction using a high register.

[jonpa]

stats.txt3 KBDownload

Here's an updated list of stats for SPEC 2006, with the latest fixes applied, and also with "soft hints" at the bottom.

[jonpa]

• Don't use VRM for VirtReg in analyzeOperands(). In case of an eviction (where VirtReg already has a physreg in VRM), this previous regclass should not be reused initially.

• Rename new Mux:es to ...MuxK.

include/llvm/CodeGen/TargetInstrInfo.h

 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineCombinerPattern.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineOutliner.h"
 #include "llvm/CodeGen/PseudoSourceValue.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/MC/MCInstrInfo.h"
 #include "llvm/Support/BranchProbability.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <utility>
 #include <vector>
public:
   virtual bool isSubregFoldable() const { return false; }
 
   /// Attempt to fold a load or store of the specified stack
   /// slot into the specified machine instruction for the specified operand(s).
   /// If this is possible, a new instruction is returned with the specified
   /// operand folded, otherwise NULL is returned.
   /// The new instruction is inserted before MI, and the client is responsible
   /// for removing the old instruction.
+  /// If VRM is passed, the assigned physregs can be inspected by target to
+  /// decide if an opcode is legal to use.
   MachineInstr *foldMemoryOperand(MachineInstr &MI, ArrayRef<unsigned> Ops,
                                   int FI,
-                                  LiveIntervals *LIS = nullptr) const;
+                                  LiveIntervals *LIS = nullptr,
+                                  VirtRegMap *VRM = nullptr) const;
 
   /// Same as the previous version except it allows folding of any load and
   /// store from / to any address, not just from a specific stack slot.
   MachineInstr *foldMemoryOperand(MachineInstr &MI, ArrayRef<unsigned> Ops,
                                   MachineInstr &LoadMI,
                                   LiveIntervals *LIS = nullptr) const;
 
   /// Return true when there is potentially a faster code sequence
protected:
   /// Target-independent code in foldMemoryOperand will
   /// take care of adding a MachineMemOperand to the newly created instruction.
   /// The instruction and any auxiliary instructions necessary will be inserted
   /// at InsertPt.
   virtual MachineInstr *
   foldMemoryOperandImpl(MachineFunction &MF, MachineInstr &MI,
                         ArrayRef<unsigned> Ops,
                         MachineBasicBlock::iterator InsertPt, int FrameIndex,
-                        LiveIntervals *LIS = nullptr) const {
+                        LiveIntervals *LIS = nullptr,
+                        VirtRegMap *VRM = nullptr) const {
     return nullptr;
   }
 
   /// Target-dependent implementation for foldMemoryOperand.
   /// Target-independent code in foldMemoryOperand will
   /// take care of adding a MachineMemOperand to the newly created instruction.
   /// The instruction and any auxiliary instructions necessary will be inserted
   /// at InsertPt.

include/llvm/CodeGen/TargetPassConfig.h

protected:
   ///
   /// Note if the target overloads addRegAssignAndRewriteOptimized, this may not
   /// be honored. This is also not generally used for the the fast variant,
   /// where the allocation and rewriting are done in one pass.
   virtual bool addPreRewrite() {
     return false;
   }
 
+  /// Add passes to be run immediately after virtual registers are rewritten
+  /// to physical registers. These passes may replace an MI with a new one,
+  /// but should preserve SlotIndexes while doing so.
+  virtual void addPostRewrite() { }
+
   /// This method may be implemented by targets that want to run passes after
   /// register allocation pass pipeline but before prolog-epilog insertion.
   virtual void addPostRegAlloc() { }
 
   /// Add passes that optimize machine instructions after register allocation.
   virtual void addMachineLateOptimization();
 
   /// This method may be implemented by targets that want to run passes after

include/llvm/CodeGen/TargetRegisterInfo.h

public:
   virtual bool getRegAllocationHints(unsigned VirtReg,
                                      ArrayRef<MCPhysReg> Order,
                                      SmallVectorImpl<MCPhysReg> &Hints,
                                      const MachineFunction &MF,
                                      const VirtRegMap *VRM = nullptr,
                                      const LiveRegMatrix *Matrix = nullptr)
     const;
 
+  /// Let target reject replacing the previously allocated phys reg with \p
+  /// NewPhysReg, by returning false. This would typically happen where
+  /// target has taken care in getRegAllocationHints() to have only a subset
+  /// of the available registers made available and it is important not to
+  /// loose this restriction.  A better solution would probably be to do like
+  /// in gcc and provide legal operand assignment combinations at the
+  /// instruction level.  On SystemZ some 32 bit instructions can use either
+  /// high or low parts of 64 bit registers, but some operand combinations
+  /// are not possible. For instance, CRMux (Compare Register) can be lowered
+  /// to C (LOW LOW), CHHR (HIGH, HIGH) or CHLR (HIGH, LOW), but (LOW, HIGH)
+  /// is *not* supported.
+  virtual bool allowHintRecoloring(unsigned VReg,
+                                   unsigned NewPhysReg,
+                                   const VirtRegMap &VRM) const {
+    return true;
+  }
+
   /// A callback to allow target a chance to update register allocation hints
   /// when a register is "changed" (e.g. coalesced) to another register.
   /// e.g. On ARM, some virtual registers should target register pairs,
   /// if one of pair is coalesced to another register, the allocation hint of
   /// the other half of the pair should be changed to point to the new register.
   virtual void updateRegAllocHint(unsigned Reg, unsigned NewReg,
                                   MachineFunction &MF) const {
     // Do nothing.

lib/CodeGen/InlineSpiller.cpp

foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>> Ops,
   // Moreover, TargetInstrInfo::foldMemoryOperand will assert if we try!
   if (FoldOps.empty())
     return false;
 
   MachineInstrSpan MIS(MI);
 
   MachineInstr *FoldMI =
       LoadMI ? TII.foldMemoryOperand(*MI, FoldOps, *LoadMI, &LIS)
-             : TII.foldMemoryOperand(*MI, FoldOps, StackSlot, &LIS);
+             : TII.foldMemoryOperand(*MI, FoldOps, StackSlot, &LIS, &VRM);
   if (!FoldMI)
     return false;
 
   // Remove LIS for any dead defs in the original MI not in FoldMI.
   for (MIBundleOperands MO(*MI); MO.isValid(); ++MO) {
     if (!MO->isReg())
       continue;
     unsigned Reg = MO->getReg();

lib/CodeGen/RegAllocGreedy.cpp

if (CurrPhys != PhysReg) {
       BlockFrequency NewCopiesCost = getBrokenHintFreq(Info, PhysReg);
       LLVM_DEBUG(dbgs() << "Old Cost: " << OldCopiesCost.getFrequency()
                         << "\nNew Cost: " << NewCopiesCost.getFrequency()
                         << '\n');
       if (OldCopiesCost < NewCopiesCost) {
         LLVM_DEBUG(dbgs() << "=> Not profitable.\n");
         continue;
       }
+
+      // Check with target for any special replacements to avoid.
+      if (!TRI->allowHintRecoloring(Reg, PhysReg, *VRM)) {
+        LLVM_DEBUG(dbgs() << "=> Not suitable.\n");
+        continue;
+      }
+
       // At this point, the cost is either cheaper or equal. If it is
       // equal, we consider this is profitable because it may expose
       // more recoloring opportunities.
       LLVM_DEBUG(dbgs() << "=> Profitable.\n");
       // Recolor the live-range.
       Matrix->unassign(LI);
       Matrix->assign(LI, PhysReg);
     }

lib/CodeGen/TargetInstrInfo.cpp

for (unsigned i = StartIdx; i < MI.getNumOperands(); ++i) {
     else
       MIB.add(MO);
   }
   return NewMI;
 }
 
 MachineInstr *TargetInstrInfo::foldMemoryOperand(MachineInstr &MI,
                                                  ArrayRef<unsigned> Ops, int FI,
-                                                 LiveIntervals *LIS) const {
+                                                 LiveIntervals *LIS,
+                                                 VirtRegMap *VRM) const {
   auto Flags = MachineMemOperand::MONone;
   for (unsigned OpIdx : Ops)
     Flags |= MI.getOperand(OpIdx).isDef() ? MachineMemOperand::MOStore
                                           : MachineMemOperand::MOLoad;
 
   MachineBasicBlock *MBB = MI.getParent();
   assert(MBB && "foldMemoryOperand needs an inserted instruction");
   MachineFunction &MF = *MBB->getParent();
if (MI.getOpcode() == TargetOpcode::STACKMAP ||
       MI.getOpcode() == TargetOpcode::PATCHPOINT ||
       MI.getOpcode() == TargetOpcode::STATEPOINT) {
     // Fold stackmap/patchpoint.
     NewMI = foldPatchpoint(MF, MI, Ops, FI, *this);
     if (NewMI)
       MBB->insert(MI, NewMI);
   } else {
     // Ask the target to do the actual folding.
-    NewMI = foldMemoryOperandImpl(MF, MI, Ops, MI, FI, LIS);
+    NewMI = foldMemoryOperandImpl(MF, MI, Ops, MI, FI, LIS, VRM);
   }
 
   if (NewMI) {
     NewMI->setMemRefs(MF, MI.memoperands());
     // Add a memory operand, foldMemoryOperandImpl doesn't do that.
     assert((!(Flags & MachineMemOperand::MOStore) ||
             NewMI->mayStore()) &&
            "Folded a def to a non-store!");

lib/CodeGen/TargetPassConfig.cpp

void TargetPassConfig::addOptimizedRegAlloc() {
   // when moving subregister definitions around, avoid this by splitting them to
   // separate vregs before. Splitting can also improve reg. allocation quality.
   addPass(&RenameIndependentSubregsID);
 
   // PreRA instruction scheduling.
   addPass(&MachineSchedulerID);
 
   if (addRegAssignmentOptimized()) {
+    // Allow targets to expand pseudo instructions depending on the choice of
+    // registers. If special requirements are involved (see comment for
+    // allowHintRecoloring()), it is important that this is done before
+    // MachineCopyPropagation.
+    addPostRewrite();
+
     // Copy propagate to forward register uses and try to eliminate COPYs that
     // were not coalesced.
     addPass(&MachineCopyPropagationID);
 
     // Run post-ra machine LICM to hoist reloads / remats.
     //
     // FIXME: can this move into MachineLateOptimization?
     addPass(&MachineLICMID);

lib/Target/AArch64/AArch64InstrInfo.h

public:
   // with subreg operands to foldMemoryOperandImpl.
   bool isSubregFoldable() const override { return true; }
 
   using TargetInstrInfo::foldMemoryOperandImpl;
   MachineInstr *
   foldMemoryOperandImpl(MachineFunction &MF, MachineInstr &MI,
                         ArrayRef<unsigned> Ops,
                         MachineBasicBlock::iterator InsertPt, int FrameIndex,
-                        LiveIntervals *LIS = nullptr) const override;
+                        LiveIntervals *LIS = nullptr,
+                        VirtRegMap *VRM = nullptr) const override;
 
   /// \returns true if a branch from an instruction with opcode \p BranchOpc
   ///  bytes is capable of jumping to a position \p BrOffset bytes away.
   bool isBranchOffsetInRange(unsigned BranchOpc,
                              int64_t BrOffset) const override;
 
   MachineBasicBlock *getBranchDestBlock(const MachineInstr &MI) const override;
 

lib/Target/AArch64/AArch64InstrInfo.cpp

if ((DestReg == AArch64::FP && SrcReg == AArch64::SP) ||
               addImm(Offset).setMIFlag(Flag);
     }
   }
 }
 
 MachineInstr *AArch64InstrInfo::foldMemoryOperandImpl(
     MachineFunction &MF, MachineInstr &MI, ArrayRef<unsigned> Ops,
     MachineBasicBlock::iterator InsertPt, int FrameIndex,
-    LiveIntervals *LIS) const {
+    LiveIntervals *LIS, VirtRegMap *VRM) const {
   // This is a bit of a hack. Consider this instruction:
   //
   //   %0 = COPY %sp; GPR64all:%0
   //
   // We explicitly chose GPR64all for the virtual register so such a copy might
   // be eliminated by RegisterCoalescer. However, that may not be possible, and
   // %0 may even spill. We can't spill %sp, and since it is in the GPR64all
   // register class, TargetInstrInfo::foldMemoryOperand() is going to try.

lib/Target/SystemZ/CMakeLists.txt

add_llvm_target(SystemZCodeGen
   SystemZInstrInfo.cpp
   SystemZLDCleanup.cpp
   SystemZLongBranch.cpp
   SystemZMachineFunctionInfo.cpp
   SystemZMachineScheduler.cpp
   SystemZMCInstLower.cpp
   SystemZRegisterInfo.cpp
   SystemZSelectionDAGInfo.cpp
+  SystemZSelectMux.cpp
   SystemZShortenInst.cpp
   SystemZSubtarget.cpp
   SystemZTargetMachine.cpp
   SystemZTargetTransformInfo.cpp
   SystemZTDC.cpp
   )
 
 add_subdirectory(AsmParser)
 add_subdirectory(Disassembler)
 add_subdirectory(InstPrinter)
 add_subdirectory(MCTargetDesc)
 add_subdirectory(TargetInfo)

lib/Target/SystemZ/SystemZ.h

 
 FunctionPass *createSystemZISelDag(SystemZTargetMachine &TM,
                                    CodeGenOpt::Level OptLevel);
 FunctionPass *createSystemZElimComparePass(SystemZTargetMachine &TM);
 FunctionPass *createSystemZExpandPseudoPass(SystemZTargetMachine &TM);
 FunctionPass *createSystemZShortenInstPass(SystemZTargetMachine &TM);
 FunctionPass *createSystemZLongBranchPass(SystemZTargetMachine &TM);
 FunctionPass *createSystemZLDCleanupPass(SystemZTargetMachine &TM);
+FunctionPass *createSystemZSelectMuxPass(SystemZTargetMachine &TM);
 FunctionPass *createSystemZTDCPass();
 } // end namespace llvm
 
 #endif

lib/Target/SystemZ/SystemZElimCompare.cpp

 #include <cassert>
 #include <cstdint>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "systemz-elim-compare"
 
 STATISTIC(BranchOnCounts, "Number of branch-on-count instructions");
+STATISTIC(LoadAndTests, "Number of load-and-test instructions");
 STATISTIC(LoadAndTraps, "Number of load-and-trap instructions");
 STATISTIC(EliminatedComparisons, "Number of eliminated comparisons");
 STATISTIC(FusedComparisons, "Number of fused compare-and-branch instructions");
 
 namespace {
 
 // Represents the references to a particular register in one or more
 // instructions.
private:
   const SystemZInstrInfo *TII = nullptr;
   const TargetRegisterInfo *TRI = nullptr;
 };
 
 char SystemZElimCompare::ID = 0;
 
 } // end anonymous namespace
 
-// Return true if CC is live out of MBB.
-static bool isCCLiveOut(MachineBasicBlock &MBB) {
-  for (auto SI = MBB.succ_begin(), SE = MBB.succ_end(); SI != SE; ++SI)
-    if ((*SI)->isLiveIn(SystemZ::CC))
-      return true;
-  return false;
-}
-
 // Returns true if MI is an instruction whose output equals the value in Reg.
 static bool preservesValueOf(MachineInstr &MI, unsigned Reg) {
   switch (MI.getOpcode()) {
   case SystemZ::LR:
   case SystemZ::LGR:
   case SystemZ::LGFR:
   case SystemZ::LTR:
   case SystemZ::LTGR:
bool SystemZElimCompare::convertToLoadAndTest(
 
   // Rebuild to get the CC operand in the right place.
   auto MIB = BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), TII->get(Opcode));
   for (const auto &MO : MI.operands())
     MIB.add(MO);
   MIB.setMemRefs(MI.memoperands());
   MI.eraseFromParent();
 
+  LoadAndTests++;
   return true;
 }
 
 // The CC users in CCUsers are testing the result of a comparison of some
 // value X against zero and we know that any CC value produced by MI would
 // also reflect the value of X.  ConvOpc may be used to pass the transfomed
 // opcode MI will have if this succeeds.  Try to adjust CCUsers so that they
 // test the result of MI directly, returning true on success.  Leave

 // Process all comparison instructions in MBB.  Return true if something
 // changed.
 bool SystemZElimCompare::processBlock(MachineBasicBlock &MBB) {
   bool Changed = false;
 
   // Walk backwards through the block looking for comparisons, recording
   // all CC users as we go.  The subroutines can delete Compare and
   // instructions before it.
-  bool CompleteCCUsers = !isCCLiveOut(MBB);
+  bool CompleteCCUsers = !SystemZRegisterInfo::isCCLiveOut(MBB);
   SmallVector<MachineInstr *, 4> CCUsers;
   MachineBasicBlock::iterator MBBI = MBB.end();
   while (MBBI != MBB.begin()) {
     MachineInstr &MI = *--MBBI;
     if (CompleteCCUsers && (MI.isCompare() || isLoadAndTestAsCmp(MI)) &&
         (optimizeCompareZero(MI, CCUsers) ||
          fuseCompareOperations(MI, CCUsers))) {
       ++MBBI;

lib/Target/SystemZ/SystemZExpandPseudo.cpp

 // pass should be run after register allocation but before the post-regalloc
 // scheduling pass.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SystemZ.h"
 #include "SystemZInstrInfo.h"
 #include "SystemZSubtarget.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 using namespace llvm;
 
 #define SYSTEMZ_EXPAND_PSEUDO_NAME "SystemZ pseudo instruction expansion pass"
 
+#define DEBUG_TYPE "systemz-expandpseudo"
+STATISTIC(MuxRotate2, "Number of Mux pseudos needing two rotates of a reg.");
+STATISTIC(MuxCmpSwap, "Number of Mux pseudo compares swapped.");
+STATISTIC(MuxCmpNonSwappable,
+          "Number of Mux pseudo compares not swappable.");
+STATISTIC(MuxCmpCCLiveOut, "Number of Mux pseudo compares with live out CC.");
+
 namespace llvm {
   void initializeSystemZExpandPseudoPass(PassRegistry&);
 }
 
 namespace {
 class SystemZExpandPseudo : public MachineFunctionPass {
 public:
   static char ID;
   SystemZExpandPseudo() : MachineFunctionPass(ID) {
     initializeSystemZExpandPseudoPass(*PassRegistry::getPassRegistry());
   }
 
   const SystemZInstrInfo *TII;
+  const TargetRegisterInfo *TRI;
+  const SystemZSubtarget *Subtarget;
 
   bool runOnMachineFunction(MachineFunction &Fn) override;
 
   StringRef getPassName() const override { return SYSTEMZ_EXPAND_PSEUDO_NAME; }
 
 private:
+  bool updateLiveInLists_CC(MachineBasicBlock &MBB);
   bool expandMBB(MachineBasicBlock &MBB);
   bool expandMI(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
                 MachineBasicBlock::iterator &NextMBBI);
   bool expandLOCRMux(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
                      MachineBasicBlock::iterator &NextMBBI);
+  bool expandAddSubMux(MachineBasicBlock::iterator MBBI);
+  bool expandCmpMux(MachineBasicBlock::iterator MBBI);
 };
 char SystemZExpandPseudo::ID = 0;
 }
 
 INITIALIZE_PASS(SystemZExpandPseudo, "systemz-expand-pseudo",
                 SYSTEMZ_EXPAND_PSEUDO_NAME, false, false)
 
 /// Returns an instance of the pseudo instruction expansion pass.
TII->copyPhysReg(*MoveMBB, MoveMBB->end(), DL, DestReg, SrcReg,
                    MI.getOperand(2).isKill());
   MoveMBB->addSuccessor(RestMBB);
 
   NextMBBI = MBB.end();
   MI.eraseFromParent();
   return true;
 }
 
+bool SystemZExpandPseudo::expandAddSubMux(MachineBasicBlock::iterator MBBI) {
+  SystemZII::MuxInfo MuxI(*MBBI, TRI);
+
+  // 1. See if legal already (after a free commute if needed).
+  if (MuxI.isAdd(TII) && MuxI.isHIGH(0) && MuxI.isLOW(1) && MuxI.isHIGH(2))
+    MuxI.commute(TII);
+  if (MuxI.selectAddSubMux(TII))
+    return true;
+  // 2. Use destination register if not used by any source operand and if it
+  // would make operands legal.
+  if (MuxI.differentRegs(0, 1) && MuxI.differentRegs(0, 2)) {
+    if (MuxI.isLOW(0)) {
+      if (MuxI.isLOW(1) && MuxI.isHIGH(2))
+        MuxI.useDstRegForOp(2, TII); // LLH -> LLL
+      else if (MuxI.isHIGH(1) && (MuxI.isLOW(2) || MuxI.sameReg(1, 2)))
+        MuxI.useDstRegForOp(1, TII); // LHL/LH0H0 -> LLL
+    }
+    else if (MuxI.isLOW(1))
+      MuxI.useDstRegForOp(1, TII); // HLX -> HHX
+  }
+  // 3. Handle the remaining cases
+  if (!MuxI.DstRegUsed) {
+    if (MuxI.isLOW(0) && MuxI.isLOW(1) && MuxI.isHIGH(2)) {
+      assert(MuxI.sameReg(0, 1) && "Case with free dst reg already handled.");
+      MuxI.RotateReg0(TRI, TII);      // LLH -> HHH
+    }
+    else if (MuxI.isLOW(0) && MuxI.isHIGH(1) && MuxI.isLOW(2)) {
+      assert(MuxI.sameReg(0, 2) && "Case with free dst reg already handled.");
+      if (MuxI.sameReg64(0, 1))
+        MuxI.commute(TII);            // LHL -> LLH
+      MuxI.RotateReg0(TRI, TII);      // LHL/LLH -> HHX
+    }
+    else if (MuxI.isLOW(0) && MuxI.isHIGH(1) && MuxI.isHIGH(2)) {
+      MuxI.RotateReg0(TRI, TII);     // LHH -> HHH/HLH/HHL/HLL
+      if (MuxI.sameReg64(0, 1))
+        MuxI.useDstRegForOp(1, TII); // HLX -> HHH
+    }
+    else if (MuxI.isHIGH(0) && MuxI.isLOW(1) && MuxI.isHIGH(2)) {
+      assert(MuxI.sameReg(0, 2) && "Case with free dst reg already handled.");
+      assert(!MuxI.isAdd(TII) && "Add was handled earlier.");
+      if (MuxI.differentRegs64(0, 1))
+        MuxI.RotateReg0(TRI, TII);    // HLH -> LLL
+      else
+        MuxI.commute(TII);            // HLH -> HHL
+    }
+  }
+  assert((MuxI.DstRegUsed || MuxI.Rotated || MuxI.Commuted) &&
+         "Should have tried to handle all cases by now.");
+
+  bool Success = MuxI.selectAddSubMux(TII);
+  assert(Success && "Expected a legal register combination by now.");
+  if (MuxI.Rotated) {
+    MuxI.RotateReg0(TRI, TII);
+    MuxRotate2++;
+  }
+
+  return true;
+}
+
+bool SystemZExpandPseudo::expandCmpMux(MachineBasicBlock::iterator MBBI) {
+  SystemZII::MuxInfo MuxI(*MBBI, TRI);
+  MachineBasicBlock *MBB = MBBI->getParent();
+
+  // 1. See if legal already
+  if (MuxI.selectCmpMux(TII))
+    return true;
+  assert(MuxI.isLOW(0) && MuxI.isHIGH(1) && "Only Cmp Lo/Hi is illegal");
+
+  // 2. Try to swap the operands if possible.
+  if (!SystemZRegisterInfo::isCCLiveOut(*MBB)) {
+    bool Swappable = true;
+    SmallVector<MachineInstr *, 4> CCUsers;
+    for (MachineBasicBlock::iterator Itr = std::next(MBBI);
+         Itr != MBB->end(); ++Itr) {
+      if (Itr->readsRegister(SystemZ::CC)) {
+        unsigned Flags = Itr->getDesc().TSFlags;
+        if ((Flags & SystemZII::CCMaskFirst) || (Flags & SystemZII::CCMaskLast))
+          CCUsers.push_back(&*Itr);
+        else {
+          Swappable = false;
+          MuxCmpNonSwappable++;
+          break;
+        }
+      }
+      if (Itr->definesRegister(SystemZ::CC))
+        break;
+    }
+    if (Swappable) {
+      assert(CCUsers.size() && "No CC users found?");
+      // Update all CC users.
+      for (unsigned Idx = 0; Idx < CCUsers.size(); ++Idx) {
+        unsigned Flags = CCUsers[Idx]->getDesc().TSFlags;
+        unsigned FirstOpNum = ((Flags & SystemZII::CCMaskFirst) ?
+                               0 : CCUsers[Idx]->getNumExplicitOperands() - 2);
+        MachineOperand &CCMaskMO = CCUsers[Idx]->getOperand(FirstOpNum + 1);
+        switch(CCMaskMO.getImm()) {
+        case SystemZ::CCMASK_CMP_LT:
+          CCMaskMO.setImm(SystemZ::CCMASK_CMP_GT);
+          break;
+        case SystemZ::CCMASK_CMP_GT:
+          CCMaskMO.setImm(SystemZ::CCMASK_CMP_LT);
+          break;
+        case SystemZ::CCMASK_CMP_LE:
+          CCMaskMO.setImm(SystemZ::CCMASK_CMP_GE);
+          break;
+        case SystemZ::CCMASK_CMP_GE:
+          CCMaskMO.setImm(SystemZ::CCMASK_CMP_LE);
+          break;
+        case SystemZ::CCMASK_CMP_EQ:
+        case SystemZ::CCMASK_CMP_NE:
+          break;
+        default:
+          llvm_unreachable("Unexpected CCMask value.");
+          break;
+        }
+      }
+      // Swap the compare operands.
+      MuxI.commute(TII);
+      bool Success = MuxI.selectCmpMux(TII);
+      assert(Success && "Expected a legal register combination by now.");
+      MuxCmpSwap++;
+      return true;
+    }
+  }
+  else
+    MuxCmpCCLiveOut++;
+
+  // 3. Use rotations.
+  MuxI.RotateReg0(TRI, TII);
+  bool Success = MuxI.selectCmpMux(TII);
+  assert(Success && "Expected a legal register combination by now.");
+  MuxI.RotateReg0(TRI, TII);
+  MuxRotate2++;
+  return true;
+}
+
 /// If MBBI references a pseudo instruction that should be expanded here,
 /// do the expansion and return true.  Otherwise return false.
 bool SystemZExpandPseudo::expandMI(MachineBasicBlock &MBB,
                                    MachineBasicBlock::iterator MBBI,
                                    MachineBasicBlock::iterator &NextMBBI) {
   MachineInstr &MI = *MBBI;
   switch (MI.getOpcode()) {
   case SystemZ::LOCRMux:
     return expandLOCRMux(MBB, MBBI, NextMBBI);
+
+  case SystemZ::CRMux:
+  case SystemZ::CLRMux:
+    return expandCmpMux(MBBI);   // XXX is it worth waiting with this?
+
+  case SystemZ::ARMux:           // XXX is it worth waiting with this?
+  case SystemZ::ARMuxK:
+  case SystemZ::ALRMux:
+  case SystemZ::ALRMuxK:
+  case SystemZ::SRMux:
+  case SystemZ::SRMuxK:
+  case SystemZ::SLRMux:
+  case SystemZ::SLRMuxK:
+    return expandAddSubMux(MBBI);
+
   default:
     break;
   }
   return false;
 }
 
 /// Iterate over the instructions in basic block MBB and expand any
 /// pseudo instructions.  Return true if anything was modified.
 bool SystemZExpandPseudo::expandMBB(MachineBasicBlock &MBB) {
   bool Modified = false;
 
   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
   while (MBBI != E) {
     MachineBasicBlock::iterator NMBBI = std::next(MBBI);
     Modified |= expandMI(MBB, MBBI, NMBBI);
     MBBI = NMBBI;
   }
 
   return Modified;
 }
 
+bool SystemZExpandPseudo::updateLiveInLists_CC(MachineBasicBlock &MBB) {
+  if (MBB.isLiveIn(SystemZ::CC))
+    return false;
+  bool Missing = false;
+  MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
+  for (; MBBI != E; ++MBBI) {
+    if (MBBI->isDebugInstr())
+      continue;
+    if (MBBI->readsRegister(SystemZ::CC)) {
+      Missing = true;
+      break;
+    }
+    if (MBBI->definesRegister(SystemZ::CC))
+      break;
+  }
+  if (Missing || (MBBI == E && SystemZRegisterInfo::isCCLiveOut(MBB))) {
+    assert(&MBB != &*MBB.getParent()->begin() &&
+           "CC can not be live-in in the entry block of the function.");
+    LLVM_DEBUG(dbgs() << "SystemZExpandPseudo: Adding missing CC to MBB "
+               << "live-in list!\n");
+    MBB.addLiveIn(SystemZ::CC);
+    return true;
+  }
+  return false;
+}
+
 bool SystemZExpandPseudo::runOnMachineFunction(MachineFunction &MF) {
   TII = static_cast<const SystemZInstrInfo *>(MF.getSubtarget().getInstrInfo());
+  Subtarget = &MF.getSubtarget<SystemZSubtarget>();
+  TRI = Subtarget->getRegisterInfo();
+
+  // We must know about all CC users when expanding CRMux, so better make
+  // sure all live-in CCs are in the live-in lists.
+  bool Change = true;
+  while (Change) {
+    Change = false;
+    for (auto &MBB : MF)
+      Change |= updateLiveInLists_CC(MBB);
+  }
 
   bool Modified = false;
   for (auto &MBB : MF)
     Modified |= expandMBB(MBB);
   return Modified;
 }
 

lib/Target/SystemZ/SystemZInstrFormats.td

 class UnaryRRPseudo<string key, SDPatternOperator operator,
                     RegisterOperand cls1, RegisterOperand cls2>
   : Pseudo<(outs cls1:$R1), (ins cls2:$R2),
            [(set cls1:$R1, (operator cls2:$R2))]> {
   let OpKey = key#cls1;
   let OpType = "reg";
 }
 
+// Like BinaryRRAndK, but expanded after RA depending on the choice of register.
+multiclass BinaryRRAndKPseudo<string key, SDPatternOperator operator,
+            RegisterOperand cls1, RegisterOperand cls2, RegisterOperand cls3> {
+  let NumOpsKey = key, Predicates = [FeatureHighWord] in {
+    let NumOpsValue = "3" in
+      def K : Pseudo<(outs cls1:$R1), (ins cls2:$R2, cls3:$R3), []>;
+    let NumOpsValue = "2", isConvertibleToThreeAddress = 1,
+        Constraints = "$R1 = $R1src" in
+      def "" : Pseudo<(outs cls1:$R1), (ins cls2:$R1src, cls3:$R3),
+               [(set cls1:$R1, (operator cls2:$R1src, cls3:$R3))]>;
+  }
+}
+
 // Like BinaryRI, but expanded after RA depending on the choice of register.
 class BinaryRIPseudo<SDPatternOperator operator, RegisterOperand cls,
                      Immediate imm>
   : Pseudo<(outs cls:$R1), (ins cls:$R1src, imm:$I2),
            [(set cls:$R1, (operator cls:$R1src, imm:$I2))]> {
   let Constraints = "$R1 = $R1src";
 }
 
class CompareRXYPseudo<SDPatternOperator operator, RegisterOperand cls,
   : Pseudo<(outs), (ins cls:$R1, mode:$XBD2),
            [(set CC, (operator cls:$R1, (load mode:$XBD2)))]> {
   let mayLoad = 1;
   let Has20BitOffset = 1;
   let HasIndex = 1;
   let AccessBytes = bytes;
 }
 
+// Like CompareRRE, but expanded after RA depending on the choice of
+// register.
+class CompareRREPseudo<SDPatternOperator operator, RegisterOperand cls1,
+                       RegisterOperand cls2>
+  : Pseudo<(outs), (ins cls1:$R1, cls2:$R2),
+           [(set CC, (operator cls1:$R1, cls2:$R2))]> {
+  let isCompare = 1;
+}
+
 // Like TestBinarySIL, but expanded later.
 class TestBinarySILPseudo<SDPatternOperator operator, Immediate imm>
   : Pseudo<(outs), (ins bdaddr12only:$BD1, imm:$I2),
            [(set CC, (operator bdaddr12only:$BD1, imm:$I2))]>;
 
 // Like CondBinaryRRF, but expanded after RA depending on the choice of
 // register.
 class CondBinaryRRFPseudo<RegisterOperand cls1, RegisterOperand cls2>

lib/Target/SystemZ/SystemZInstrInfo.h

class SystemZInstrInfo : public SystemZGenInstrInfo {
   void expandRIPseudo(MachineInstr &MI, unsigned LowOpcode, unsigned HighOpcode,
                       bool ConvertHigh) const;
   void expandRIEPseudo(MachineInstr &MI, unsigned LowOpcode,
                        unsigned LowOpcodeK, unsigned HighOpcode) const;
   void expandRXYPseudo(MachineInstr &MI, unsigned LowOpcode,
                        unsigned HighOpcode) const;
   void expandLOCPseudo(MachineInstr &MI, unsigned LowOpcode,
                        unsigned HighOpcode) const;
-  void expandLOCRPseudo(MachineInstr &MI, unsigned LowOpcode,
-                        unsigned HighOpcode) const;
   void expandZExtPseudo(MachineInstr &MI, unsigned LowOpcode,
                         unsigned Size) const;
   void expandLoadStackGuard(MachineInstr *MI) const;
 
   MachineInstrBuilder
   emitGRX32Move(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
                 const DebugLoc &DL, unsigned DestReg, unsigned SrcReg,
                 unsigned LowLowOpcode, unsigned Size, bool KillSrc,
void loadRegFromStackSlot(MachineBasicBlock &MBB,
                             const TargetRegisterInfo *TRI) const override;
   MachineInstr *convertToThreeAddress(MachineFunction::iterator &MFI,
                                       MachineInstr &MI,
                                       LiveVariables *LV) const override;
   MachineInstr *
   foldMemoryOperandImpl(MachineFunction &MF, MachineInstr &MI,
                         ArrayRef<unsigned> Ops,
                         MachineBasicBlock::iterator InsertPt, int FrameIndex,
-                        LiveIntervals *LIS = nullptr) const override;
+                        LiveIntervals *LIS = nullptr,
+                        VirtRegMap *VRM = nullptr) const override;
   MachineInstr *foldMemoryOperandImpl(
       MachineFunction &MF, MachineInstr &MI, ArrayRef<unsigned> Ops,
       MachineBasicBlock::iterator InsertPt, MachineInstr &LoadMI,
       LiveIntervals *LIS = nullptr) const override;
   bool expandPostRAPseudo(MachineInstr &MBBI) const override;
   bool reverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const
     override;
 
public:
   // aliasing information, that two MIs access different memory
   // addresses. This function returns true if two MIs access different
   // memory addresses and false otherwise.
   bool
   areMemAccessesTriviallyDisjoint(MachineInstr &MIa, MachineInstr &MIb,
                                   AliasAnalysis *AA = nullptr) const override;
 };
 
+namespace SystemZII {
+struct MuxInfo {
+  MachineInstr *MI;
+  unsigned PseudoOpcode;
+  unsigned NumOps;
+  MachineBasicBlock *MBB;
+  DebugLoc DL;
+  unsigned Regs[3];
+  unsigned Regs64[3];
+  bool Rotated;
+  bool Commuted;
+  bool DstRegUsed;
+  MuxInfo(MachineInstr &mi_, const TargetRegisterInfo *TRI);
+  bool isHIGH(unsigned Idx) {
+    assert(Idx < NumOps && "Operand index out of range.");
+    return SystemZ::GRH32BitRegClass.contains(Regs[Idx]);
+  }
+  bool isLOW(unsigned Idx) { return !isHIGH(Idx); }
+  bool sameReg(unsigned A, unsigned B) { return Regs[A] == Regs[B]; }
+  bool differentRegs(unsigned A, unsigned B) { return !sameReg(A, B); }
+  bool sameReg64(unsigned A, unsigned B) { return Regs64[A] == Regs64[B]; }
+  bool differentRegs64(unsigned A, unsigned B) { return !sameReg64(A, B); }
+  void useDstRegForOp(unsigned Idx, const SystemZInstrInfo *TII);
+  void RotateReg0(const TargetRegisterInfo *TRI,
+                  const SystemZInstrInfo *TII);
+  void negateRHSIfSub(const SystemZInstrInfo *TII);
+  void commute(const SystemZInstrInfo *TII);
+  bool selectAddSubMux(const SystemZInstrInfo *TII,
+                       SlotIndexes *SI = nullptr);
+  bool selectCmpMux(const SystemZInstrInfo *TII);
+  bool isAdd(const SystemZInstrInfo *TII) const {
+    return TII->get(PseudoOpcode).isCommutable();
+  }
+};
+} // end namespace SystemZII
+
 } // end namespace llvm
 
 #endif // LLVM_LIB_TARGET_SYSTEMZ_SYSTEMZINSTRINFO_H

lib/Target/SystemZ/SystemZInstrInfo.cpp

 
 using namespace llvm;
 
 #define GET_INSTRINFO_CTOR_DTOR
 #define GET_INSTRMAP_INFO
 #include "SystemZGenInstrInfo.inc"
 
 #define DEBUG_TYPE "systemz-II"
-STATISTIC(LOCRMuxJumps, "Number of LOCRMux jump-sequences (lower is better)");
+STATISTIC(PREGCOPIES, "Number of copies between allocatable physregs");
+STATISTIC(MuxCopyDst, "Number of Mux pseudos needing a copy to dst.");
+STATISTIC(FOLDEDMEMOPS, "Number of memops folded.");
 
 // Return a mask with Count low bits set.
 static uint64_t allOnes(unsigned int Count) {
   return Count == 0 ? 0 : (uint64_t(1) << (Count - 1) << 1) - 1;
 }
 
 // Reg should be a 32-bit GPR.  Return true if it is a high register rather
 // than a low register.

 // register is a low GR32 and HighOpcode if the register is a high GR32.
 void SystemZInstrInfo::expandLOCPseudo(MachineInstr &MI, unsigned LowOpcode,
                                        unsigned HighOpcode) const {
   unsigned Reg = MI.getOperand(0).getReg();
   unsigned Opcode = isHighReg(Reg) ? HighOpcode : LowOpcode;
   MI.setDesc(get(Opcode));
 }
 
-// MI is a load-register-on-condition pseudo instruction.  Replace it with
-// LowOpcode if source and destination are both low GR32s and HighOpcode if
-// source and destination are both high GR32s.
-void SystemZInstrInfo::expandLOCRPseudo(MachineInstr &MI, unsigned LowOpcode,
-                                        unsigned HighOpcode) const {
-  unsigned DestReg = MI.getOperand(0).getReg();
-  unsigned SrcReg = MI.getOperand(2).getReg();
-  bool DestIsHigh = isHighReg(DestReg);
-  bool SrcIsHigh = isHighReg(SrcReg);
-
-  if (!DestIsHigh && !SrcIsHigh)
-    MI.setDesc(get(LowOpcode));
-  else if (DestIsHigh && SrcIsHigh)
-    MI.setDesc(get(HighOpcode));
-  else
-    LOCRMuxJumps++;
-
-  // If we were unable to implement the pseudo with a single instruction, we
-  // need to convert it back into a branch sequence.  This cannot be done here
-  // since the caller of expandPostRAPseudo does not handle changes to the CFG
-  // correctly.  This change is defered to the SystemZExpandPseudo pass.
-}
-
 // MI is an RR-style pseudo instruction that zero-extends the low Size bits
 // of one GRX32 into another.  Replace it with LowOpcode if both operands
 // are low registers, otherwise use RISB[LH]G.
 void SystemZInstrInfo::expandZExtPseudo(MachineInstr &MI, unsigned LowOpcode,
                                         unsigned Size) const {
   MachineInstrBuilder MIB =
     emitGRX32Move(*MI.getParent(), MI, MI.getDebugLoc(),
                MI.getOperand(0).getReg(), MI.getOperand(1).getReg(), LowOpcode,
MachineInstrBuilder(*MBB.getParent(), std::prev(MBBI))
       .addReg(SrcReg, RegState::Implicit);
     copyPhysReg(MBB, MBBI, DL, RI.getSubReg(DestReg, SystemZ::subreg_l64),
                 RI.getSubReg(SrcReg, SystemZ::subreg_l64), KillSrc);
     MachineInstrBuilder(*MBB.getParent(), std::prev(MBBI))
       .addReg(SrcReg, (getKillRegState(KillSrc) | RegState::Implicit));
     return;
   }
 
+  PREGCOPIES++;
+
   if (SystemZ::GRX32BitRegClass.contains(DestReg, SrcReg)) {
     emitGRX32Move(MBB, MBBI, DL, DestReg, SrcReg, SystemZ::LR, 32, KillSrc,
                   false);
     return;
   }
 
   // Move 128-bit floating-point values between VR128 and FP128.
   if (SystemZ::VR128BitRegClass.contains(DestReg) &&
if (LogicOp And = interpretAndImmediate(Opcode)) {
     }
   }
   return nullptr;
 }
 
 MachineInstr *SystemZInstrInfo::foldMemoryOperandImpl(
     MachineFunction &MF, MachineInstr &MI, ArrayRef<unsigned> Ops,
     MachineBasicBlock::iterator InsertPt, int FrameIndex,
-    LiveIntervals *LIS) const {
+    LiveIntervals *LIS, VirtRegMap *VRM) const {
   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
+  MachineRegisterInfo &MRI = MF.getRegInfo();
   const MachineFrameInfo &MFI = MF.getFrameInfo();
   unsigned Size = MFI.getObjectSize(FrameIndex);
   unsigned Opcode = MI.getOpcode();
 
   if (Ops.size() == 2 && Ops[0] == 0 && Ops[1] == 1) {
     if (LIS != nullptr && (Opcode == SystemZ::LA || Opcode == SystemZ::LAY) &&
         isInt<8>(MI.getOperand(2).getImm()) && !MI.getOperand(3).getReg()) {
 
if (LIS != nullptr && (Opcode == SystemZ::LA || Opcode == SystemZ::LAY) &&
         // LA(Y) %reg, CONST(%reg) -> AGSI %mem, CONST
         MachineInstr *BuiltMI = BuildMI(*InsertPt->getParent(), InsertPt,
                                         MI.getDebugLoc(), get(SystemZ::AGSI))
                                     .addFrameIndex(FrameIndex)
                                     .addImm(0)
                                     .addImm(MI.getOperand(2).getImm());
         BuiltMI->findRegisterDefOperand(SystemZ::CC)->setIsDead(true);
         CCLiveRange.createDeadDef(MISlot, LIS->getVNInfoAllocator());
+        FOLDEDMEMOPS++;
         return BuiltMI;
       }
     }
     return nullptr;
   }
 
   // All other cases require a single operand.
   if (Ops.size() != 1)
if ((Opcode == SystemZ::AHI || Opcode == SystemZ::AGHI) && OpNum == 0 &&
     // A(G)HI %reg, CONST -> A(G)SI %mem, CONST
     Opcode = (Opcode == SystemZ::AHI ? SystemZ::ASI : SystemZ::AGSI);
     MachineInstr *BuiltMI =
         BuildMI(*InsertPt->getParent(), InsertPt, MI.getDebugLoc(), get(Opcode))
             .addFrameIndex(FrameIndex)
             .addImm(0)
             .addImm(MI.getOperand(2).getImm());
     transferDeadCC(&MI, BuiltMI);
+    FOLDEDMEMOPS++;
     return BuiltMI;
   }
 
   if ((Opcode == SystemZ::ALFI && OpNum == 0 &&
        isInt<8>((int32_t)MI.getOperand(2).getImm())) ||
       (Opcode == SystemZ::ALGFI && OpNum == 0 &&
        isInt<8>((int64_t)MI.getOperand(2).getImm()))) {
     // AL(G)FI %reg, CONST -> AL(G)SI %mem, CONST
     Opcode = (Opcode == SystemZ::ALFI ? SystemZ::ALSI : SystemZ::ALGSI);
     MachineInstr *BuiltMI =
         BuildMI(*InsertPt->getParent(), InsertPt, MI.getDebugLoc(), get(Opcode))
             .addFrameIndex(FrameIndex)
             .addImm(0)
             .addImm((int8_t)MI.getOperand(2).getImm());
     transferDeadCC(&MI, BuiltMI);
+    FOLDEDMEMOPS++;
     return BuiltMI;
   }
 
   if ((Opcode == SystemZ::SLFI && OpNum == 0 &&
        isInt<8>((int32_t)-MI.getOperand(2).getImm())) ||
       (Opcode == SystemZ::SLGFI && OpNum == 0 &&
        isInt<8>((int64_t)-MI.getOperand(2).getImm()))) {
     // SL(G)FI %reg, CONST -> AL(G)SI %mem, -CONST
     Opcode = (Opcode == SystemZ::SLFI ? SystemZ::ALSI : SystemZ::ALGSI);
     MachineInstr *BuiltMI =
         BuildMI(*InsertPt->getParent(), InsertPt, MI.getDebugLoc(), get(Opcode))
             .addFrameIndex(FrameIndex)
             .addImm(0)
             .addImm((int8_t)-MI.getOperand(2).getImm());
     transferDeadCC(&MI, BuiltMI);
+    FOLDEDMEMOPS++;
     return BuiltMI;
   }
 
   if (Opcode == SystemZ::LGDR || Opcode == SystemZ::LDGR) {
     bool Op0IsGPR = (Opcode == SystemZ::LGDR);
     bool Op1IsGPR = (Opcode == SystemZ::LDGR);
     // If we're spilling the destination of an LDGR or LGDR, store the
     // source register instead.
     if (OpNum == 0) {
       unsigned StoreOpcode = Op1IsGPR ? SystemZ::STG : SystemZ::STD;
+      FOLDEDMEMOPS++;
       return BuildMI(*InsertPt->getParent(), InsertPt, MI.getDebugLoc(),
                      get(StoreOpcode))
           .add(MI.getOperand(1))
           .addFrameIndex(FrameIndex)
           .addImm(0)
           .addReg(0);
     }
     // If we're spilling the source of an LDGR or LGDR, load the
     // destination register instead.
     if (OpNum == 1) {
       unsigned LoadOpcode = Op0IsGPR ? SystemZ::LG : SystemZ::LD;
+      FOLDEDMEMOPS++;
       return BuildMI(*InsertPt->getParent(), InsertPt, MI.getDebugLoc(),
                      get(LoadOpcode))
         .add(MI.getOperand(0))
         .addFrameIndex(FrameIndex)
         .addImm(0)
         .addReg(0);
     }
   }
MachineInstr *SystemZInstrInfo::foldMemoryOperandImpl(
   // might be equal.  We don't worry about that case here, because spill slot
   // coloring happens later, and because we have special code to remove
   // MVCs that turn out to be redundant.
   if (OpNum == 0 && MI.hasOneMemOperand()) {
     MachineMemOperand *MMO = *MI.memoperands_begin();
     if (MMO->getSize() == Size && !MMO->isVolatile() && !MMO->isAtomic()) {
       // Handle conversion of loads.
       if (isSimpleBD12Move(&MI, SystemZII::SimpleBDXLoad)) {
+        FOLDEDMEMOPS++;
         return BuildMI(*InsertPt->getParent(), InsertPt, MI.getDebugLoc(),
                        get(SystemZ::MVC))
             .addFrameIndex(FrameIndex)
             .addImm(0)
             .addImm(Size)
             .add(MI.getOperand(1))
             .addImm(MI.getOperand(2).getImm())
             .addMemOperand(MMO);
       }
       // Handle conversion of stores.
       if (isSimpleBD12Move(&MI, SystemZII::SimpleBDXStore)) {
+        FOLDEDMEMOPS++;
         return BuildMI(*InsertPt->getParent(), InsertPt, MI.getDebugLoc(),
                        get(SystemZ::MVC))
             .add(MI.getOperand(1))
             .addImm(MI.getOperand(2).getImm())
             .addImm(Size)
             .addFrameIndex(FrameIndex)
             .addImm(0)
             .addMemOperand(MMO);
       }
     }
   }
 
-  // If the spilled operand is the final one, try to change <INSN>R
-  // into <INSN>.
-  int MemOpcode = SystemZ::getMemOpcode(Opcode);
+  // If the spilled operand is the final one, try to change <INSN>R into
+  // <INSN>.  These Muxes may have a suitable memory instruction. It seems to
+  // work best to decide on a high/low opcode at this point and constrain the
+  // register class accordingly if needed.
+  int MemOpcode = -1;
+  const TargetRegisterClass *Op0RC32 = nullptr;
+  switch(Opcode) {
+  case SystemZ::ARMux:
+  case SystemZ::ALRMux:
+  case SystemZ::SRMux:
+  case SystemZ::SLRMux:
+  case SystemZ::CRMux:
+  case SystemZ::CLRMux: {
+    MachineOperand &MO = MI.getOperand(0);
+    // Only try this whith a virtual register and a provided VRM.
+    if (TRI->isVirtualRegister(MO.getReg()) && VRM != nullptr)
+      Op0RC32 = RI.getRC32(MO, VRM, &MRI);
+    break;
+  }
+  default: break;
+  }
+  const TargetRegisterClass *ConstrainedRC = nullptr;
+  if (Op0RC32 != nullptr) {
+    if (Op0RC32 != &SystemZ::GRH32BitRegClass) {
+      switch(Opcode) {
+      case SystemZ::ARMux:
+        MemOpcode = SystemZ::A;
+        break;
+      case SystemZ::ALRMux:
+        MemOpcode = SystemZ::AL;
+        break;
+      case SystemZ::SRMux:
+        MemOpcode = SystemZ::S;
+        break;
+      case SystemZ::SLRMux:
+        MemOpcode = SystemZ::SL;
+        break;
+      case SystemZ::CRMux:
+        MemOpcode = SystemZ::C;
+        break;
+      case SystemZ::CLRMux:
+        MemOpcode = SystemZ::CL;
+        break;
+      default: break;
+      }
+      assert(MemOpcode != -1 && "Should have a opcode for low-part by now.");
+      ConstrainedRC = &SystemZ::GR32BitRegClass;
+    } else {
+      switch(Opcode) {
+      case SystemZ::CRMux:
+        MemOpcode = SystemZ::CHF;
+        break;
+      case SystemZ::CLRMux:
+        MemOpcode = SystemZ::CLHF;
+        break;
+      default: break;
+      }
+      if (MemOpcode != -1)
+        ConstrainedRC = &SystemZ::GRH32BitRegClass;
+    }
+  }
+  if (MemOpcode == -1)
+    MemOpcode = SystemZ::getMemOpcode(Opcode);
   if (MemOpcode >= 0) {
     unsigned NumOps = MI.getNumExplicitOperands();
     if (OpNum == NumOps - 1) {
       const MCInstrDesc &MemDesc = get(MemOpcode);
       uint64_t AccessBytes = SystemZII::getAccessSize(MemDesc.TSFlags);
       assert(AccessBytes != 0 && "Size of access should be known");
       assert(AccessBytes <= Size && "Access outside the frame index");
       uint64_t Offset = Size - AccessBytes;
       MachineInstrBuilder MIB = BuildMI(*InsertPt->getParent(), InsertPt,
                                         MI.getDebugLoc(), get(MemOpcode));
       for (unsigned I = 0; I < OpNum; ++I)
         MIB.add(MI.getOperand(I));
       MIB.addFrameIndex(FrameIndex).addImm(Offset);
       if (MemDesc.TSFlags & SystemZII::HasIndex)
         MIB.addReg(0);
       transferDeadCC(&MI, MIB);
+      if (ConstrainedRC != nullptr) {
+        unsigned Reg = MIB->getOperand(0).getReg();
+        if (MRI.getRegClass(Reg) == &SystemZ::GRX32BitRegClass)
+          MRI.constrainRegClass(Reg, ConstrainedRC);
+      }
+      FOLDEDMEMOPS++;
       return MIB;
     }
   }
 
   return nullptr;
 }
 
 MachineInstr *SystemZInstrInfo::foldMemoryOperandImpl(
bool SystemZInstrInfo::expandPostRAPseudo(MachineInstr &MI) const {
   case SystemZ::LOCMux:
     expandLOCPseudo(MI, SystemZ::LOC, SystemZ::LOCFH);
     return true;
 
   case SystemZ::LOCHIMux:
     expandLOCPseudo(MI, SystemZ::LOCHI, SystemZ::LOCHHI);
     return true;
 
-  case SystemZ::LOCRMux:
-    expandLOCRPseudo(MI, SystemZ::LOCR, SystemZ::LOCFHR);
-    return true;
-
   case SystemZ::STCMux:
     expandRXYPseudo(MI, SystemZ::STC, SystemZ::STCH);
     return true;
 
   case SystemZ::STHMux:
     expandRXYPseudo(MI, SystemZ::STH, SystemZ::STHH);
     return true;
 
bool SystemZInstrInfo::expandPostRAPseudo(MachineInstr &MI) const {
   case SystemZ::AHIMuxK:
     expandRIEPseudo(MI, SystemZ::AHI, SystemZ::AHIK, SystemZ::AIH);
     return true;
 
   case SystemZ::AFIMux:
     expandRIPseudo(MI, SystemZ::AFI, SystemZ::AIH, false);
     return true;
 
-  case SystemZ::CHIMux:
-    expandRIPseudo(MI, SystemZ::CHI, SystemZ::CIH, false);
-    return true;
-
-  case SystemZ::CFIMux:
-    expandRIPseudo(MI, SystemZ::CFI, SystemZ::CIH, false);
-    return true;
-
   case SystemZ::CLFIMux:
     expandRIPseudo(MI, SystemZ::CLFI, SystemZ::CLIH, false);
     return true;
 
   case SystemZ::CMux:
     expandRXYPseudo(MI, SystemZ::C, SystemZ::CHF);
     return true;
 
if (SameVal) {
     int HighOffset = OffsetA < OffsetB ? OffsetB : OffsetA;
     int LowWidth = (LowOffset == OffsetA) ? WidthA : WidthB;
     if (LowOffset + LowWidth <= HighOffset)
       return true;
   }
 
   return false;
 }
+
+SystemZII::MuxInfo::MuxInfo(MachineInstr &mi_,
+                            const TargetRegisterInfo *TRI) : MI(&mi_) {
+  PseudoOpcode = mi_.getOpcode();
+  NumOps = (MI->isCompare() ?  2 : 3);
+  MBB = MI->getParent();
+  DL = MI->getDebugLoc();
+  for (unsigned OpIdx = 0; OpIdx < NumOps; ++OpIdx) {
+    Regs[OpIdx] = MI->getOperand(OpIdx).getReg();
+    assert(SystemZ::GRX32BitRegClass.contains(Regs[OpIdx]) &&
+           "Expected a GRX32 register operand.");
+    unsigned SubRegIdx = (SystemZ::GR32BitRegClass.contains(Regs[OpIdx]) ?
+                          SystemZ::subreg_l32 : SystemZ::subreg_h32);
+    Regs64[OpIdx] = TRI->getMatchingSuperReg(Regs[OpIdx], SubRegIdx,
+                                             &SystemZ::GR64BitRegClass);
+  }
+  Rotated = false;
+  Commuted = false;
+  DstRegUsed = false;
+}
+
+void SystemZII::MuxInfo::useDstRegForOp(unsigned Idx,
+                                        const SystemZInstrInfo *TII) {
+  TII->copyPhysReg(*MBB, MI, DL, Regs[0], Regs[Idx], false/*KillSrc*/);
+  unsigned ReplacedReg = Regs[Idx];
+  for (unsigned OpIdx = 1; OpIdx < NumOps; ++OpIdx)
+    if (Regs[OpIdx] == ReplacedReg) {
+      Regs[OpIdx] = Regs[0];
+      Regs64[OpIdx] = Regs64[0];
+    }
+  MuxCopyDst++;
+  DstRegUsed = true;
+}
+
+void SystemZII::MuxInfo::RotateReg0(const TargetRegisterInfo *TRI,
+                                    const SystemZInstrInfo *TII) {
+  // Put the second rotation after MI.
+  MachineBasicBlock::iterator MBBI = MI;
+  MachineBasicBlock::iterator InsPos = (Rotated ? std::next(MBBI) : MBBI);
+  BuildMI(*MBB, InsPos, DL, TII->get(SystemZ::RLLG), Regs64[0])
+    .addReg(Regs64[0]).addReg(0).addImm(32);
+  unsigned Reg = Regs[0];
+  unsigned OtherSubRegIdx =
+    isLOW(0) ? SystemZ::subreg_h32 :  SystemZ::subreg_l32;
+  unsigned OtherReg = TRI->getSubReg(Regs64[0], OtherSubRegIdx);
+  for (unsigned Idx = 0; Idx < NumOps; ++Idx) {
+    if (Regs[Idx] == Reg)
+      Regs[Idx] = OtherReg;
+    else if (Regs[Idx] == OtherReg)
+      Regs[Idx] = Reg;
+  }
+  Rotated = true;
+}
+
+void SystemZII::MuxInfo::negateRHSIfSub(const SystemZInstrInfo *TII) {
+  switch(PseudoOpcode)  {
+  case SystemZ::SRMux:
+  case SystemZ::SRMuxK:
+    PseudoOpcode = SystemZ::ARMux;
+    break;
+  case SystemZ::SLRMux:
+  case SystemZ::SLRMuxK:
+    PseudoOpcode = SystemZ::ALRMux;
+    break;
+  default:
+    return;
+  }
+  if (isLOW(2)) {
+    BuildMI(*MBB, MI, DL, TII->get(SystemZ::LNR), Regs[2])
+      .addReg(Regs[2]);
+  } else {
+    BuildMI(*MBB, MI, DL, TII->get(SystemZ::XIHF), Regs[2])
+      .addReg(Regs[2])
+      .addImm(0xffffffff);
+    BuildMI(*MBB, MI, DL, TII->get(SystemZ::AIH), Regs[2])
+      .addReg(Regs[2])
+      .addImm(1);
+  }
+}
+
+void SystemZII::MuxInfo::commute(const SystemZInstrInfo *TII) {
+  negateRHSIfSub(TII);
+
+  unsigned LHS = (NumOps == 3 ? 1 : 0);
+  unsigned RHS = (NumOps == 3 ? 2 : 1);
+  unsigned RegTmp = Regs[RHS];
+  Regs[RHS] = Regs[LHS];
+  Regs[LHS] = RegTmp;
+  RegTmp = Regs64[RHS];
+  Regs64[RHS] = Regs64[LHS];
+  Regs64[LHS] = RegTmp;
+  Commuted = true;
+}
+
+bool SystemZII::MuxInfo::selectAddSubMux(const SystemZInstrInfo *TII,
+                                         SlotIndexes *SI) {
+  unsigned LowOpcode, HiOpcode, HiHiLoOpcode;
+  if (PseudoOpcode == SystemZ::ARMux || PseudoOpcode == SystemZ::ARMuxK) {
+    LowOpcode = SystemZ::AR;
+    HiOpcode = SystemZ::AHHHR;
+    HiHiLoOpcode = SystemZ::AHHLR;
+  }
+  else if (PseudoOpcode == SystemZ::SRMux || PseudoOpcode == SystemZ::SRMuxK) {
+    LowOpcode = SystemZ::SR;
+    HiOpcode = SystemZ::SHHHR;
+    HiHiLoOpcode = SystemZ::SHHLR;
+  }
+  else if (PseudoOpcode == SystemZ::ALRMux || PseudoOpcode == SystemZ::ALRMuxK) {
+    LowOpcode = SystemZ::ALR;
+    HiOpcode = SystemZ::ALHHHR;
+    HiHiLoOpcode = SystemZ::ALHHLR;
+  }
+  else if (PseudoOpcode == SystemZ::SLRMux || PseudoOpcode == SystemZ::SLRMuxK) {
+    LowOpcode = SystemZ::SLR;
+    HiOpcode = SystemZ::SLHHHR;
+    HiHiLoOpcode = SystemZ::SLHHLR;
+  }
+  else
+    llvm_unreachable("Bad opcode.");
+
+  unsigned Opcode = 0;
+  if (isLOW(0) && isLOW(1) && isLOW(2))
+    Opcode = (Regs[0] == Regs[1] ?
+              LowOpcode : SystemZ::getThreeOperandOpcode(LowOpcode));
+  else if (isHIGH(0) && isHIGH(1) && isHIGH(2))
+    Opcode = HiOpcode;
+  else if (isHIGH(0) && isHIGH(1) && isLOW(2))
+    Opcode = HiHiLoOpcode;
+  else
+    return false;
+  MachineInstr *NewMI = BuildMI(*MBB, MI, DL, TII->get(Opcode), Regs[0])
+                          .addReg(Regs[1])
+                          .addReg(Regs[2]);
+  if (SI != nullptr)
+    SI->replaceMachineInstrInMaps(*MI, *NewMI);
+  MI->eraseFromParent();
+  MI = NewMI;
+  return true;
+}
+
+bool SystemZII::MuxInfo::selectCmpMux(const SystemZInstrInfo *TII) {
+  unsigned LowOpcode, HiOpcode, HiLowOpcode;
+  if (PseudoOpcode == SystemZ::CRMux) {
+    LowOpcode = SystemZ::CR;
+    HiOpcode = SystemZ::CHHR;
+    HiLowOpcode = SystemZ::CHLR;
+  } else if (PseudoOpcode == SystemZ::CLRMux) {
+    LowOpcode = SystemZ::CLR;
+    HiOpcode = SystemZ::CLHHR;
+    HiLowOpcode = SystemZ::CLHLR;
+  } else
+    llvm_unreachable("Bad opcode.");
+
+  unsigned Opcode = 0;
+  if (isLOW(0) && isLOW(1))
+    Opcode = LowOpcode;
+  else if (isHIGH(0) && isHIGH(1))
+    Opcode = HiOpcode;
+  else if (isHIGH(0) && isLOW(1))
+    Opcode = HiLowOpcode;
+  else
+    return false;
+  if (Commuted || Rotated)
+    for (unsigned OpIdx = 0; OpIdx < 2; ++OpIdx) {
+      MachineOperand &MO = MI->getOperand(OpIdx);
+      MO.setReg(Regs[OpIdx]);
+      MO.setIsKill(false);
+    }
+  MI->setDesc(TII->get(Opcode));
+  return true;
+}

lib/Target/SystemZ/SystemZInstrInfo.td

 //===----------------------------------------------------------------------===//
 // Addition
 //===----------------------------------------------------------------------===//
 
 // Addition producing a signed overflow flag.
 let Defs = [CC], CCValues = 0xF, CompareZeroCCMask = 0x8 in {
   // Addition of a register.
   let isCommutable = 1 in {
+    // Expands to AR(K), AHHHR or AHHLR, depending on the choice of register.
+    defm ARMux : BinaryRRAndKPseudo<"armux", z_sadd, GRX32, GRX32, GRX32>;
     defm AR : BinaryRRAndK<"ar", 0x1A, 0xB9F8, z_sadd, GR32, GR32>;
     defm AGR : BinaryRREAndK<"agr", 0xB908, 0xB9E8, z_sadd, GR64, GR64>;
   }
   def AGFR : BinaryRRE<"agfr", 0xB918, null_frag, GR64, GR32>;
 
   // Addition to a high register.
   def AHHHR : BinaryRRFa<"ahhhr", 0xB9C8, null_frag, GRH32, GRH32, GRH32>,
               Requires<[FeatureHighWord]>;
let Defs = [CC], CCValues = 0xF, CompareZeroCCMask = 0x8 in {
   def AGSI : BinarySIY<"agsi", 0xEB7A, add, imm64sx8>;
 }
 defm : SXB<z_sadd, GR64, AGFR>;
 
 // Addition producing a carry.
 let Defs = [CC] in {
   // Addition of a register.
   let isCommutable = 1 in {
+    // Expands to ALR(K), ALHHHR or ALHHLR, depending on the choice of register.
+    defm ALRMux : BinaryRRAndKPseudo<"alrmux", z_uadd, GRX32, GRX32, GRX32>;
     defm ALR : BinaryRRAndK<"alr", 0x1E, 0xB9FA, z_uadd, GR32, GR32>;
     defm ALGR : BinaryRREAndK<"algr", 0xB90A, 0xB9EA, z_uadd, GR64, GR64>;
   }
   def ALGFR : BinaryRRE<"algfr", 0xB91A, null_frag, GR64, GR32>;
 
   // Addition to a high register.
   def ALHHHR : BinaryRRFa<"alhhhr", 0xB9CA, null_frag, GRH32, GRH32, GRH32>,
                Requires<[FeatureHighWord]>;

 
 //===----------------------------------------------------------------------===//
 // Subtraction
 //===----------------------------------------------------------------------===//
 
 // Subtraction producing a signed overflow flag.
 let Defs = [CC], CCValues = 0xF, CompareZeroCCMask = 0x8 in {
   // Subtraction of a register.
+  // Expands to SR(K), SHHHR or SHHLR, depending on the choice of register.
+  defm SRMux : BinaryRRAndKPseudo<"srmux", z_ssub, GRX32, GRX32, GRX32>;
   defm SR : BinaryRRAndK<"sr", 0x1B, 0xB9F9, z_ssub, GR32, GR32>;
   def SGFR : BinaryRRE<"sgfr", 0xB919, null_frag, GR64, GR32>;
   defm SGR : BinaryRREAndK<"sgr", 0xB909, 0xB9E9, z_ssub, GR64, GR64>;
 
   // Subtraction from a high register.
   def SHHHR : BinaryRRFa<"shhhr", 0xB9C9, null_frag, GRH32, GRH32, GRH32>,
               Requires<[FeatureHighWord]>;
   def SHHLR : BinaryRRFa<"shhlr", 0xB9D9, null_frag, GRH32, GRH32, GR32>,

 def : Pat<(z_saddo GR64:$src1, imm64lh16n:$src2),
           (SGR GR64:$src1, (LLILH imm64lh16n:$src2))>;
 def : Pat<(z_saddo GR64:$src1, imm64lf32n:$src2),
           (SGR GR64:$src1, (LLILF imm64lf32n:$src2))>;
 
 // Subtraction producing a carry.
 let Defs = [CC] in {
   // Subtraction of a register.
+  // Expands to SLR(K), SLHHHR or SLHHLR, depending on the choice of register.
+  defm SLRMux : BinaryRRAndKPseudo<"slrmux", z_usub, GRX32, GRX32, GRX32>;
   defm SLR : BinaryRRAndK<"slr", 0x1F, 0xB9FB, z_usub, GR32, GR32>;
   def SLGFR : BinaryRRE<"slgfr", 0xB91B, null_frag, GR64, GR32>;
   defm SLGR : BinaryRREAndK<"slgr", 0xB90B, 0xB9EB, z_usub, GR64, GR64>;
 
   // Subtraction from a high register.
   def SLHHHR : BinaryRRFa<"slhhhr", 0xB9CB, null_frag, GRH32, GRH32, GRH32>,
                Requires<[FeatureHighWord]>;
   def SLHHLR : BinaryRRFa<"slhhlr", 0xB9DB, null_frag, GRH32, GRH32, GR32>,

 //===----------------------------------------------------------------------===//
 // Comparison
 //===----------------------------------------------------------------------===//
 
 // Signed comparisons.  We put these before the unsigned comparisons because
 // some of the signed forms have COMPARE AND BRANCH equivalents whereas none
 // of the unsigned forms do.
 let Defs = [CC], CCValues = 0xE in {
-  // Comparison with a register.
+  // Comparison with a register.  CRMux expands to CR, CHHR or CHLR,
+  // depending on the choice of register.
+  def CRMux : CompareRREPseudo<z_scmp, GRX32, GRX32>,
+              Requires<[FeatureHighWord]>;
   def CR   : CompareRR <"cr",   0x19,   z_scmp,    GR32, GR32>;
   def CGFR : CompareRRE<"cgfr", 0xB930, null_frag, GR64, GR32>;
   def CGR  : CompareRRE<"cgr",  0xB920, z_scmp,    GR64, GR64>;
 
   // Comparison with a high register.
   def CHHR : CompareRRE<"chhr", 0xB9CD, null_frag, GRH32, GRH32>,
              Requires<[FeatureHighWord]>;
   def CHLR : CompareRRE<"chlr", 0xB9DD, null_frag, GRH32, GR32>,
let Defs = [CC], CCValues = 0xE in {
   def CHHSI : CompareSIL<"chhsi", 0xE554, z_scmp, asextloadi16, imm32sx16>;
   def CHSI  : CompareSIL<"chsi",  0xE55C, z_scmp, load, imm32sx16>;
   def CGHSI : CompareSIL<"cghsi", 0xE558, z_scmp, load, imm64sx16>;
 }
 defm : SXB<z_scmp, GR64, CGFR>;
 
 // Unsigned comparisons.
 let Defs = [CC], CCValues = 0xE, IsLogical = 1 in {
-  // Comparison with a register.
+  // Comparison with a register.  CLRMux expands to CLR, CLHHR or CLHLR,
+  // depending on the choice of register.
+  def CLRMux : CompareRREPseudo<z_ucmp, GRX32, GRX32>,
+               Requires<[FeatureHighWord]>;
   def CLR   : CompareRR <"clr",   0x15,   z_ucmp,    GR32, GR32>;
   def CLGFR : CompareRRE<"clgfr", 0xB931, null_frag, GR64, GR32>;
   def CLGR  : CompareRRE<"clgr",  0xB921, z_ucmp,    GR64, GR64>;
 
   // Comparison with a high register.
   def CLHHR : CompareRRE<"clhhr", 0xB9CF, null_frag, GRH32, GRH32>,
               Requires<[FeatureHighWord]>;
   def CLHLR : CompareRRE<"clhlr", 0xB9DF, null_frag, GRH32, GR32>,

lib/Target/SystemZ/SystemZRegisterInfo.h

public:
   }
 
   /// getCrossCopyRegClass - Returns a legal register class to copy a register
   /// in the specified class to or from. Returns NULL if it is possible to copy
   /// between a two registers of the specified class.
   const TargetRegisterClass *
   getCrossCopyRegClass(const TargetRegisterClass *RC) const override;
 
+  static bool isCCLiveOut(MachineBasicBlock &MBB);
+  const TargetRegisterClass* getRC32(MachineOperand &MO,
+                                     const VirtRegMap *VRM,
+                                     const MachineRegisterInfo *MRI) const;
   bool getRegAllocationHints(unsigned VirtReg,
                              ArrayRef<MCPhysReg> Order,
                              SmallVectorImpl<MCPhysReg> &Hints,
                              const MachineFunction &MF,
                              const VirtRegMap *VRM,
                              const LiveRegMatrix *Matrix) const override;
+  bool allowHintRecoloring(unsigned VReg,
+                           unsigned NewPhysReg,
+                           const VirtRegMap &VRM) const override;
 
   // Override TargetRegisterInfo.h.
   bool requiresRegisterScavenging(const MachineFunction &MF) const override {
     return true;
   }
   bool requiresFrameIndexScavenging(const MachineFunction &MF) const override {
     return true;
   }

lib/Target/SystemZ/SystemZRegisterInfo.cpp

 #include "llvm/CodeGen/TargetFrameLowering.h"
 #include "llvm/CodeGen/VirtRegMap.h"
 
 using namespace llvm;
 
 #define GET_REGINFO_TARGET_DESC
 #include "SystemZGenRegisterInfo.inc"
 
+#define DEBUG_TYPE "regalloc"
+
 SystemZRegisterInfo::SystemZRegisterInfo()
     : SystemZGenRegisterInfo(SystemZ::R14D) {}
 
 // Given that MO is a GRX32 operand, return either GR32 or GRH32 if MO
 // somehow belongs in it. Otherwise, return GRX32.
-static const TargetRegisterClass *getRC32(MachineOperand &MO,
-                                          const VirtRegMap *VRM,
-                                          const MachineRegisterInfo *MRI) {
+const TargetRegisterClass*
+SystemZRegisterInfo::getRC32(MachineOperand &MO,
+                             const MachineRegisterInfo *MRI) const {
   const TargetRegisterClass *RC = MRI->getRegClass(MO.getReg());
-
   if (SystemZ::GR32BitRegClass.hasSubClassEq(RC) ||
       MO.getSubReg() == SystemZ::subreg_l32 ||
       MO.getSubReg() == SystemZ::subreg_hl32)
     return &SystemZ::GR32BitRegClass;
   if (SystemZ::GRH32BitRegClass.hasSubClassEq(RC) ||
       MO.getSubReg() == SystemZ::subreg_h32 ||
       MO.getSubReg() == SystemZ::subreg_hh32)
     return &SystemZ::GRH32BitRegClass;
 
   if (VRM && VRM->hasPhys(MO.getReg())) {
     unsigned PhysReg = VRM->getPhys(MO.getReg());
     if (SystemZ::GR32BitRegClass.contains(PhysReg))
       return &SystemZ::GR32BitRegClass;
     assert (SystemZ::GRH32BitRegClass.contains(PhysReg) &&
             "Phys reg not in GR32 or GRH32?");
     return &SystemZ::GRH32BitRegClass;
   }
 
-  assert (RC == &SystemZ::GRX32BitRegClass);
+  assert(RC == &SystemZ::GRX32BitRegClass);
   return RC;
 }
 
 // Pass the registers of RC as hints while making sure that if any of these
 // registers are copy hints (and therefore already in Hints), hint them
 // first.
 static void addHints(ArrayRef<MCPhysReg> Order,
                      SmallVectorImpl<MCPhysReg> &Hints,
                      const TargetRegisterClass *RC,
                      const MachineRegisterInfo *MRI) {
   SmallSet<unsigned, 4> CopyHints;
   CopyHints.insert(Hints.begin(), Hints.end());
   Hints.clear();
   for (MCPhysReg Reg : Order)
     if (CopyHints.count(Reg) &&
         RC->contains(Reg) && !MRI->isReserved(Reg))
       Hints.push_back(Reg);
   for (MCPhysReg Reg : Order)
     if (!CopyHints.count(Reg) &&
         RC->contains(Reg) && !MRI->isReserved(Reg))
       Hints.push_back(Reg);
 }
 
+// EXPERIMENTAL
+#include "llvm/Support/CommandLine.h"
+static cl::opt<bool> HARDHIORLO("hard-hi-or-lo", cl::init(false));
+static cl::opt<bool> SOFTHIORLO("soft-hi-or-lo", cl::init(false));
+static cl::opt<bool> HARD_LT_HINTS("hard-lt-hints", cl::init(false));
+static cl::opt<bool> HARD_LL_CH_HINTS("hard-ll-ch-hints", cl::init(false));
+
+bool SystemZRegisterInfo::isCCLiveOut(MachineBasicBlock &MBB) {
+  for (auto SI = MBB.succ_begin(), SE = MBB.succ_end(); SI != SE; ++SI)
+    if ((*SI)->isLiveIn(SystemZ::CC))
+      return true;
+  return false;
+}
+
 bool
 SystemZRegisterInfo::getRegAllocationHints(unsigned VirtReg,
                                            ArrayRef<MCPhysReg> Order,
                                            SmallVectorImpl<MCPhysReg> &Hints,
                                            const MachineFunction &MF,
                                            const VirtRegMap *VRM,
                                            const LiveRegMatrix *Matrix) const {
   const MachineRegisterInfo *MRI = &MF.getRegInfo();
-  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
 
   bool BaseImplRetVal = TargetRegisterInfo::getRegAllocationHints(
       VirtReg, Order, Hints, MF, VRM, Matrix);
 
   if (MRI->getRegClass(VirtReg) == &SystemZ::GRX32BitRegClass) {
+    // A map from virtual registers to their register classes.
+    struct Reg2RCMap : std::map<MCPhysReg, const TargetRegisterClass *> {
+      unsigned VirtReg_;
+      bool Change;
+      const TargetRegisterClass *SoftHintRC;
+      Reg2RCMap(unsigned Reg) : VirtReg_(Reg) { reset(); }
+      void reset() {
+        Change = false;
+        SoftHintRC = nullptr;
+      }
+      void findRC(MachineOperand &MO,
+                  const VirtRegMap *VRM,
+                  const MachineRegisterInfo *MRI,
+                  const SystemZRegisterInfo *TRI) {
+        if (find(MO.getReg()) != end())
+          return;
+        const TargetRegisterClass *RC = TRI->getRC32(MO, VRM, MRI);
+        (*this)[MO.getReg()] = RC;
+      }
+      void constrainReg(unsigned Reg, const TargetRegisterClass *RC,
+                        bool HardHint = true) {
+        assert((RC == &SystemZ::GR32BitRegClass ||
+                RC == &SystemZ::GRH32BitRegClass) &&
+               "Should constrain to either low or high parts.");
+        if (!HardHint) {
+          if (Reg == VirtReg_)
+            SoftHintRC = RC;
+          return;
+        }
+        if ((*this)[Reg] == &SystemZ::GRX32BitRegClass) {
+          (*this)[Reg] = RC;
+          Change = true;
+        } else if ((*this)[Reg] != nullptr && (*this)[Reg] != RC) {
+          // Don't hint either way if the opposite RC is also needed.
+          (*this)[Reg] = nullptr;
+          Change = true;
+        }
+      }
+    } Reg2RC(VirtReg);
+    // Search all use/def connected instructions iteratively to propagate the
+    // requirements of registers being in either GR32 or GR32H. At the end,
+    // pass hints for VirtReg if either GR32 or GR32H is the result.
+    const TargetRegisterClass *LOW = &SystemZ::GR32BitRegClass;
+    const TargetRegisterClass *HIGH = &SystemZ::GRH32BitRegClass;
     SmallVector<unsigned, 8> Worklist;
     SmallSet<unsigned, 4> DoneRegs;
+    Reg2RC.Change = true;
+    while (Reg2RC.Change) {
+      Reg2RC.reset();
+      Worklist.clear();
       Worklist.push_back(VirtReg);
+      DoneRegs.clear();
       while (Worklist.size()) {
         unsigned Reg = Worklist.pop_back_val();
         if (!DoneRegs.insert(Reg).second)
           continue;
+        for (MachineInstr &MI : MRI->reg_nodbg_instructions(Reg)) {
+          unsigned Regs[3] = {0, 0, 0};
+          bool HasHigh = false;
+          bool HasLow = false;
+          unsigned OpI = 0;
+          auto processOperands = [&](unsigned NumOps) -> void {
+            assert(NumOps <= 3 && "Index out of range.");
+            for (; OpI < NumOps; ++OpI) {
+              MachineOperand &MO = MI.getOperand(OpI);
+              Regs[OpI] = MO.getReg();
+              Reg2RC.findRC(MO, VRM, MRI, this);
+              // Add GRX32 registers to worklist
+              if (Reg2RC[MO.getReg()] == &SystemZ::GRX32BitRegClass)
+                Worklist.push_back(MO.getReg());
+              else if (Reg2RC[MO.getReg()] == HIGH)
+                HasHigh = true;
+              else
+                HasLow = true;
+            }
+          };
+          // Add hints for all operands to make them all high or low if
+          // possible, to avoid the slower High/Low instructions. If
+          // OnlyExtra is false, give hard hints. If OnlyExtra is true, give
+          // hard or soft hints only if one of the experimental CL options
+          // for this was given.
+          auto addHiOrLoHints = [&](bool OnlyExtra) -> void {
+            if (!HARDHIORLO && !SOFTHIORLO && OnlyExtra)
+              return;
+            bool HintHard = (OnlyExtra ? HARDHIORLO : true);
+            const TargetRegisterClass *RC = nullptr;
+            if (HasHigh && !HasLow)
+              RC = HIGH;
+            else if (HasLow && !HasHigh)
+              RC = LOW;
+            if (RC != nullptr)
+              for (unsigned Idx = 0; Regs[Idx] && Idx < 3; ++Idx)
+                Reg2RC.constrainReg(Regs[Idx], RC, HintHard);
+          };
+
+          switch (MI.getOpcode()) {
+          case SystemZ::CRMux:
+          case SystemZ::CLRMux:
+            processOperands(2);
+            // Avoid needing to rotate the LH case.
+            if (isCCLiveOut(*MI.getParent())) {
+              // L_ -> LL
+              if (Reg2RC[Regs[0]] == LOW)
+                Reg2RC.constrainReg(Regs[1], LOW);
+              // _H -> HH
+              else if (Reg2RC[Regs[1]] == HIGH)
+                Reg2RC.constrainReg(Regs[0], HIGH);
+            }
+            addHiOrLoHints(true/*OnlyExtra*/);
+            break;
 
-      for (auto &Use : MRI->use_instructions(Reg)) {
-        // For LOCRMux, see if the other operand is already a high or low
-        // register, and in that case give the correpsonding hints for
-        // VirtReg. LOCR instructions need both operands in either high or
-        // low parts.
-        if (Use.getOpcode() == SystemZ::LOCRMux) {
-          MachineOperand &TrueMO = Use.getOperand(1);
-          MachineOperand &FalseMO = Use.getOperand(2);
-          const TargetRegisterClass *RC =
-            TRI->getCommonSubClass(getRC32(FalseMO, VRM, MRI),
-                                   getRC32(TrueMO, VRM, MRI));
-          if (RC && RC != &SystemZ::GRX32BitRegClass) {
-            addHints(Order, Hints, RC, MRI);
-            // Return true to make these hints the only regs available to
-            // RA. This may mean extra spilling but since the alternative is
-            // a jump sequence expansion of the LOCRMux, it is preferred.
-            return true;
+          case SystemZ::SRMux:
+          case SystemZ::SRMuxK:
+          case SystemZ::SLRMux:
+          case SystemZ::SLRMuxK:
+            processOperands(3);
+            // H__ -> HH_
+            if (Reg2RC[Regs[0]] == HIGH) {
+              Reg2RC.constrainReg(Regs[1], HIGH);
+              break;
             }
+            // _L_ -> LLL
+            if (Reg2RC[Regs[1]] == LOW) {
+              Reg2RC.constrainReg(Regs[0], LOW);
+              Reg2RC.constrainReg(Regs[2], LOW);
+              break;
+            }
+            LLVM_FALLTHROUGH;
+          case SystemZ::ARMux:
+          case SystemZ::ARMuxK:
+          case SystemZ::ALRMux:
+          case SystemZ::ALRMuxK:
+            processOperands(3);
+            // L__ -> LLL
+            if (Reg2RC[Regs[0]] == LOW) {
+              Reg2RC.constrainReg(Regs[1], LOW);
+              Reg2RC.constrainReg(Regs[2], LOW);
+            }
+            // _LL -> LLL
+            else if (Reg2RC[Regs[1]] == LOW && Reg2RC[Regs[2]] == LOW)
+              Reg2RC.constrainReg(Regs[0], LOW);
+            else if (Reg2RC[Regs[0]] == HIGH) {
+              // HL_ -> HLH
+              if (Reg2RC[Regs[1]] == LOW)
+                Reg2RC.constrainReg(Regs[2], HIGH);
+              // H_L -> HHL
+              else if (Reg2RC[Regs[2]] == LOW)
+                Reg2RC.constrainReg(Regs[1], HIGH);
+              // Hrr -> HHH
+              else if (Regs[1] == Regs[2])
+                Reg2RC.constrainReg(Regs[1], HIGH);
+            }
+            // _H? -> HH?
+            else if (Reg2RC[Regs[1]] == HIGH || Reg2RC[Regs[2]] == HIGH)
+              Reg2RC.constrainReg(Regs[0], HIGH);
+            addHiOrLoHints(true/*OnlyExtra*/);
+            break;
+
+          case SystemZ::LOCRMux:
+            processOperands(3);
+            addHiOrLoHints(false/*OnlyExtra*/);
+            break;
+
+          case SystemZ::LLCMux:
+          case SystemZ::LLHMux:
+            processOperands(1);
+            Reg2RC.constrainReg(Regs[0], LOW, HARD_LL_CH_HINTS/*HardHint*/);
+            break;
 
-          // Add the other operand of the LOCRMux to the worklist.
-          unsigned OtherReg =
-            (TrueMO.getReg() == Reg ? FalseMO.getReg() : TrueMO.getReg());
-          if (MRI->getRegClass(OtherReg) == &SystemZ::GRX32BitRegClass)
-            Worklist.push_back(OtherReg);
-        } // end LOCRMux
-        else if (Use.getOpcode() == SystemZ::CHIMux ||
-                 Use.getOpcode() == SystemZ::CFIMux) {
-          if (Use.getOperand(1).getImm() == 0) {
+          case SystemZ::CHIMux:
+          case SystemZ::CFIMux:
+            processOperands(1);
+            if (MI.getOperand(1).getImm() == 0) {
               bool OnlyLMuxes = true;
-            for (MachineInstr &DefMI : MRI->def_instructions(VirtReg))
+              for (MachineInstr &DefMI : MRI->def_instructions(Reg))
                 if (DefMI.getOpcode() != SystemZ::LMux)
                   OnlyLMuxes = false;
-            if (OnlyLMuxes) {
-              addHints(Order, Hints, &SystemZ::GR32BitRegClass, MRI);
-              // Return false to make these hints preferred but not obligatory.
-              return false;
+              if (OnlyLMuxes)
+                Reg2RC.constrainReg(Regs[0], LOW, HARD_LT_HINTS/*HardHint*/);
             }
+            break;
+
+          default: break;
           }
-        } // end CHIMux / CFIMux
-      }
+        } // MI
+      } // Worklist
+    } // Change
+    const TargetRegisterClass *ResultRC = Reg2RC[VirtReg];
+    if (ResultRC == nullptr)
+      return BaseImplRetVal;
+    if (ResultRC != &SystemZ::GRX32BitRegClass) {
+      assert ((ResultRC == LOW || ResultRC == HIGH) && "Bad Regclass.");
+      addHints(Order, Hints, ResultRC, MRI);
+      return true;
+    if (Reg2RC.SoftHintRC != nullptr) {
+      assert ((Reg2RC.SoftHintRC == LOW || Reg2RC.SoftHintRC == HIGH) &&
+              "Bad Regclass.");
+      addHints(Order, Hints, Reg2RC.SoftHintRC, MRI);
+      return false;
     }
   }
 
   return BaseImplRetVal;
 }
 
+bool SystemZRegisterInfo::allowHintRecoloring(unsigned VReg,
+                                              unsigned NewPhysReg,
+                                              const VirtRegMap &VRM) const {
+  if (!SystemZ::GRX32BitRegClass.contains(NewPhysReg))
+    return true;
+  unsigned CurrPhys = VRM.getPhys(VReg);
+  assert(SystemZ::GRX32BitRegClass.contains(CurrPhys) && "Expected GRX32 reg.");
+  if (SystemZ::GR32BitRegClass.contains(CurrPhys) ==
+      SystemZ::GR32BitRegClass.contains(NewPhysReg))
+    return true;
+
+  // This is a GRX32 register that has changed between low and high parts.
+  MachineRegisterInfo *MRI = &VRM.getRegInfo();
+  for (const MachineInstr &MI : MRI->reg_nodbg_instructions(VReg))
+    switch (MI.getOpcode()) {
+    case SystemZ::LOCRMux:
+    case SystemZ::CRMux:
+    case SystemZ::CLRMux:
+    case SystemZ::SRMuxK:
+    case SystemZ::SLRMuxK:
+    case SystemZ::SRMux:
+    case SystemZ::SLRMux:
+    case SystemZ::ARMux:
+    case SystemZ::ARMuxK:
+    case SystemZ::ALRMux:
+    case SystemZ::ALRMuxK:
+      LLVM_DEBUG(dbgs() << "SystemZ: Avoiding replacing "
+                 << getName(CurrPhys) << " with "
+                 << getName(NewPhysReg) << " in "; MI.dump());
+      return false;
+    default: break;
+    }
+
+  return true;
+}
+
 const MCPhysReg *
 SystemZRegisterInfo::getCalleeSavedRegs(const MachineFunction *MF) const {
   const SystemZSubtarget &Subtarget = MF->getSubtarget<SystemZSubtarget>();
   if (MF->getFunction().getCallingConv() == CallingConv::AnyReg)
     return Subtarget.hasVector()? CSR_SystemZ_AllRegs_Vector_SaveList
                                 : CSR_SystemZ_AllRegs_SaveList;
   if (MF->getSubtarget().getTargetLowering()->supportSwiftError() &&
       MF->getFunction().getAttributes().hasAttrSomewhere(

lib/Target/SystemZ/SystemZScheduleZ13.td

def : InstRW<[WLat1LSU, WLat1LSU, RegReadAdv, FXa, LSU, NormalGr],
              (instregex "ALG(F)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "ALGHSIK$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "ALGF(I|R)$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "ALGR(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "ALR(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "AR(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "A(L)?HHHR$")>;
 def : InstRW<[WLat2, WLat2, FXa, NormalGr], (instregex "A(L)?HHLR$")>;
+def : InstRW<[WLat1, FXa, NormalGr], (instregex "A(L)?RMux(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "ALSIH(N)?$")>;
 def : InstRW<[WLat2LSU, FXb, LSU, NormalGr], (instregex "A(L)?(G)?SI$")>;
 
 // Logical addition with carry
 def : InstRW<[WLat2LSU, WLat2LSU, RegReadAdv, FXa, LSU, GroupAlone],
              (instregex "ALC(G)?$")>;
 def : InstRW<[WLat2, WLat2, FXa, GroupAlone], (instregex "ALC(G)?R$")>;
 

 def : InstRW<[WLat1LSU, WLat1LSU, RegReadAdv, FXa, LSU, NormalGr],
              (instregex "SL(G|GF|Y)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "SLGF(I|R)$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "SLGR(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "SLR(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "SR(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "S(L)?HHHR$")>;
 def : InstRW<[WLat2, WLat2, FXa, NormalGr], (instregex "S(L)?HHLR$")>;
+def : InstRW<[WLat1, FXa, NormalGr], (instregex "S(L)?RMux(K)?$")>;
 
 // Subtraction with borrow
 def : InstRW<[WLat2LSU, WLat2LSU, RegReadAdv, FXa, LSU, GroupAlone],
              (instregex "SLB(G)?$")>;
 def : InstRW<[WLat2, WLat2, FXa, GroupAlone], (instregex "SLB(G)?R$")>;
 
 // Subtraction with sign extension (32 -> 64)
 def : InstRW<[WLat2LSU, WLat2LSU, RegReadAdv, FXa, LSU, NormalGr],

 def : InstRW<[WLat1LSU, RegReadAdv, FXb, LSU, NormalGr], (instregex "CLHF$")>;
 def : InstRW<[WLat1LSU, FXb, LSU, NormalGr], (instregex "CLH(RL|HSI)$")>;
 def : InstRW<[WLat1, FXb, NormalGr], (instregex "CLIH$")>;
 def : InstRW<[WLat1LSU, FXb, LSU, NormalGr], (instregex "CLI(Y)?$")>;
 def : InstRW<[WLat1, FXb, NormalGr], (instregex "CLR$")>;
 def : InstRW<[WLat1LSU, FXb, LSU, NormalGr], (instregex "CLRL$")>;
 def : InstRW<[WLat1, FXb, NormalGr], (instregex "C(L)?HHR$")>;
 def : InstRW<[WLat2, FXb, NormalGr], (instregex "C(L)?HLR$")>;
+def : InstRW<[WLat1, FXb, NormalGr], (instregex "C(L)?RMux")>;
 
 // Compare halfword
 def : InstRW<[WLat2LSU, RegReadAdv, FXb, LSU, NormalGr], (instregex "CH(Y)?$")>;
 def : InstRW<[WLat2LSU, FXb, LSU, NormalGr], (instregex "CHRL$")>;
 def : InstRW<[WLat2LSU, RegReadAdv, FXb, LSU, NormalGr], (instregex "CGH$")>;
 def : InstRW<[WLat2LSU, FXb, LSU, NormalGr], (instregex "CGHRL$")>;
 def : InstRW<[WLat2LSU, FXa, FXb, LSU, Cracked], (instregex "CHHSI$")>;
 

lib/Target/SystemZ/SystemZScheduleZ14.td

def : InstRW<[WLat1LSU, WLat1LSU, RegReadAdv, FXa, LSU, NormalGr],
              (instregex "ALG(F)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "ALGHSIK$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "ALGF(I|R)$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "ALGR(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "ALR(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "AR(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "A(L)?HHHR$")>;
 def : InstRW<[WLat2, WLat2, FXa, NormalGr], (instregex "A(L)?HHLR$")>;
+def : InstRW<[WLat1, FXa, NormalGr], (instregex "A(L)?RMux(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "ALSIH(N)?$")>;
 def : InstRW<[WLat2LSU, FXb, LSU, NormalGr], (instregex "A(L)?(G)?SI$")>;
 
 // Logical addition with carry
 def : InstRW<[WLat2LSU, WLat2LSU, RegReadAdv, FXa, LSU, GroupAlone],
              (instregex "ALC(G)?$")>;
 def : InstRW<[WLat2, WLat2, FXa, GroupAlone], (instregex "ALC(G)?R$")>;
 

 def : InstRW<[WLat1LSU, WLat1LSU, RegReadAdv, FXa, LSU, NormalGr],
              (instregex "SL(G|GF|Y)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "SLGF(I|R)$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "SLGR(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "SLR(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "SR(K)?$")>;
 def : InstRW<[WLat1, FXa, NormalGr], (instregex "S(L)?HHHR$")>;
 def : InstRW<[WLat2, WLat2, FXa, NormalGr], (instregex "S(L)?HHLR$")>;
+def : InstRW<[WLat1, FXa, NormalGr], (instregex "S(L)?RMux(K)?$")>;
 
 // Subtraction with borrow
 def : InstRW<[WLat2LSU, WLat2LSU, RegReadAdv, FXa, LSU, GroupAlone],
              (instregex "SLB(G)?$")>;
 def : InstRW<[WLat2, WLat2, FXa, GroupAlone], (instregex "SLB(G)?R$")>;
 
 // Subtraction with sign extension (16/32 -> 64)
 def : InstRW<[WLat2LSU, WLat2LSU, RegReadAdv, FXa, LSU, NormalGr],

 def : InstRW<[WLat1LSU, RegReadAdv, FXb, LSU, NormalGr], (instregex "CLHF$")>;
 def : InstRW<[WLat1LSU, FXb, LSU, NormalGr], (instregex "CLH(RL|HSI)$")>;
 def : InstRW<[WLat1, FXb, NormalGr], (instregex "CLIH$")>;
 def : InstRW<[WLat1LSU, FXb, LSU, NormalGr], (instregex "CLI(Y)?$")>;
 def : InstRW<[WLat1, FXb, NormalGr], (instregex "CLR$")>;
 def : InstRW<[WLat1LSU, FXb, LSU, NormalGr], (instregex "CLRL$")>;
 def : InstRW<[WLat1, FXb, NormalGr], (instregex "C(L)?HHR$")>;
 def : InstRW<[WLat2, FXb, NormalGr], (instregex "C(L)?HLR$")>;
+def : InstRW<[WLat1, FXb, NormalGr], (instregex "C(L)?RMux")>;
 
 // Compare halfword
 def : InstRW<[WLat2LSU, RegReadAdv, FXb, LSU, NormalGr], (instregex "CH(Y)?$")>;
 def : InstRW<[WLat2LSU, FXb, LSU, NormalGr], (instregex "CHRL$")>;
 def : InstRW<[WLat2LSU, RegReadAdv, FXb, LSU, NormalGr], (instregex "CGH$")>;
 def : InstRW<[WLat2LSU, FXb, LSU, NormalGr], (instregex "CGHRL$")>;
 def : InstRW<[WLat2LSU, FXa, FXb, LSU, Cracked], (instregex "CHHSI$")>;
 

lib/Target/SystemZ/SystemZScheduleZ196.td

def : InstRW<[WLat1LSU, WLat1LSU, RegReadAdv, FXU, LSU, NormalGr],
              (instregex "ALGF$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "ALGHSIK$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "ALGF(I|R)$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "ALGR(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "ALR(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "AR(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "A(L)?HHHR$")>;
 def : InstRW<[WLat2, WLat2, FXU2, GroupAlone], (instregex "A(L)?HHLR$")>;
+def : InstRW<[WLat1, FXU, NormalGr], (instregex "A(L)?RMux(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "ALSIH(N)?$")>;
 def : InstRW<[WLat1LSU, WLat1LSU, RegReadAdv, FXU, LSU, NormalGr],
              (instregex "A(L)?G$")>;
 def : InstRW<[WLat1LSU, FXU, LSU, NormalGr], (instregex "A(L)?GSI$")>;
 
 // Logical addition with carry
 def : InstRW<[WLat2LSU, WLat2LSU, RegReadAdv, FXU, LSU, GroupAlone],
              (instregex "ALC(G)?$")>;

 def : InstRW<[WLat1LSU, WLat1LSU, RegReadAdv, FXU, LSU, NormalGr],
              (instregex "SL(G|GF|Y)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "SLGF(I|R)$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "SLGR(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "SLR(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "SR(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "S(L)?HHHR$")>;
 def : InstRW<[WLat2, WLat2, FXU2, GroupAlone], (instregex "S(L)?HHLR$")>;
+def : InstRW<[WLat1, FXU, NormalGr], (instregex "S(L)?RMux(K)?$")>;
 
 // Subtraction with borrow
 def : InstRW<[WLat2LSU, WLat2LSU, RegReadAdv, FXU, LSU, GroupAlone],
              (instregex "SLB(G)?$")>;
 def : InstRW<[WLat2, WLat2, FXU, GroupAlone], (instregex "SLB(G)?R$")>;
 
 // Subtraction with sign extension (32 -> 64)
 def : InstRW<[WLat2LSU, WLat2LSU, RegReadAdv, FXU2, LSU, GroupAlone],

 def : InstRW<[WLat1LSU, RegReadAdv, FXU, LSU, NormalGr], (instregex "CLHF$")>;
 def : InstRW<[WLat1LSU, FXU, LSU, NormalGr], (instregex "CLH(RL|HSI)$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "CLIH$")>;
 def : InstRW<[WLat1LSU, FXU, LSU, NormalGr], (instregex "CLI(Y)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "CLR$")>;
 def : InstRW<[WLat1LSU, FXU, LSU, NormalGr], (instregex "CLRL$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "C(L)?HHR$")>;
 def : InstRW<[WLat2, FXU2, GroupAlone], (instregex "C(L)?HLR$")>;
+def : InstRW<[WLat1, FXU, NormalGr], (instregex "C(L)?RMux")>;
 
 // Compare halfword
 def : InstRW<[WLat2LSU, RegReadAdv, FXU2, LSU, GroupAlone],
              (instregex "CH(Y)?$")>;
 def : InstRW<[WLat2LSU, FXU2, LSU, GroupAlone], (instregex "CHRL$")>;
 def : InstRW<[WLat2LSU, RegReadAdv, FXU2, LSU, GroupAlone], (instregex "CGH$")>;
 def : InstRW<[WLat2LSU, FXU2, LSU, GroupAlone], (instregex "CGHRL$")>;
 def : InstRW<[WLat2LSU, FXU2, LSU, GroupAlone], (instregex "CHHSI$")>;

lib/Target/SystemZ/SystemZScheduleZEC12.td

def : InstRW<[WLat1LSU, WLat1LSU, RegReadAdv, FXU, LSU, NormalGr],
              (instregex "ALGF$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "ALGHSIK$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "ALGF(I|R)$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "ALGR(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "ALR(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "AR(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "A(L)?HHHR$")>;
 def : InstRW<[WLat2, WLat2, FXU, NormalGr], (instregex "A(L)?HHLR$")>;
+def : InstRW<[WLat1, FXU, NormalGr], (instregex "A(L)?RMux(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "ALSIH(N)?$")>;
 def : InstRW<[WLat1LSU, WLat1LSU, RegReadAdv, FXU, LSU, NormalGr],
              (instregex "A(L)?G$")>;
 def : InstRW<[WLat1LSU, FXU, LSU, NormalGr], (instregex "A(L)?GSI$")>;
 
 // Logical addition with carry
 def : InstRW<[WLat2LSU, WLat2LSU, RegReadAdv, FXU, LSU, GroupAlone],
              (instregex "ALC(G)?$")>;

 def : InstRW<[WLat1LSU, WLat1LSU, RegReadAdv, FXU, LSU, NormalGr],
              (instregex "SL(G|GF|Y)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "SLGF(I|R)$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "SLGR(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "SLR(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "SR(K)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "S(L)?HHHR$")>;
 def : InstRW<[WLat2, WLat2, FXU, NormalGr], (instregex "S(L)?HHLR$")>;
+def : InstRW<[WLat1, FXU, NormalGr], (instregex "S(L)?RMux(K)?$")>;
 
 // Subtraction with borrow
 def : InstRW<[WLat2LSU, WLat2LSU, RegReadAdv, FXU, LSU, GroupAlone],
              (instregex "SLB(G)?$")>;
 def : InstRW<[WLat2, WLat2, FXU, GroupAlone], (instregex "SLB(G)?R$")>;
 
 // Subtraction with sign extension (32 -> 64)
 def : InstRW<[WLat2LSU, WLat2LSU, RegReadAdv, FXU, LSU, NormalGr],

 def : InstRW<[WLat1LSU, RegReadAdv, FXU, LSU, NormalGr], (instregex "CLHF$")>;
 def : InstRW<[WLat1LSU, FXU, LSU, NormalGr], (instregex "CLH(RL|HSI)$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "CLIH$")>;
 def : InstRW<[WLat1LSU, FXU, LSU, NormalGr], (instregex "CLI(Y)?$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "CLR$")>;
 def : InstRW<[WLat1LSU, FXU, LSU, NormalGr], (instregex "CLRL$")>;
 def : InstRW<[WLat1, FXU, NormalGr], (instregex "C(L)?HHR$")>;
 def : InstRW<[WLat2, FXU, NormalGr], (instregex "C(L)?HLR$")>;
+def : InstRW<[WLat1, FXU, NormalGr], (instregex "C(L)?RMux")>;
 
 // Compare halfword
 def : InstRW<[WLat2LSU, RegReadAdv, FXU, LSU, NormalGr], (instregex "CH(Y)?$")>;
 def : InstRW<[WLat2LSU, FXU, LSU, NormalGr], (instregex "CHRL$")>;
 def : InstRW<[WLat2LSU, RegReadAdv, FXU, LSU, NormalGr], (instregex "CGH$")>;
 def : InstRW<[WLat2LSU, FXU, LSU, NormalGr], (instregex "CGHRL$")>;
 def : InstRW<[WLat2LSU, FXU2, LSU, GroupAlone], (instregex "CHHSI$")>;
 

lib/Target/SystemZ/SystemZSelectMux.cpp

+//==------- SystemZSelectMux.cpp - Select Mux instructions --------*- C++ -*-=//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains a pass that is run immediately after VirtRegRewriter
+// and before MachineCopyPropagation. The purpose is to set the opcodes of
+// GRX32 Mux pseudos to match the choice of registers which have been
+// carefully hinted during register allocation. It is important to do this
+// before any later pass might substitute a register for another without
+// knowledge of the actual legal combinations of high/low register
+// assignments.
+//
+//===----------------------------------------------------------------------===//
+
+#include "SystemZ.h"
+#include "SystemZInstrInfo.h"
+#include "SystemZSubtarget.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/LiveStacks.h"
+#include "llvm/CodeGen/SlotIndexes.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+using namespace llvm;
+
+#define SYSTEMZ_EXPAND_PSEUDO_NAME "SystemZ Mux pseudo selection pass"
+
+#define DEBUG_TYPE "systemz-selectmux"
+STATISTIC(LOCRMuxJumps, "Number of LOCRMux jump-sequences (lower is better)");
+STATISTIC(LOCRs, "Number of LOCRs");
+STATISTIC(MUXLOWs, "Number of Muxes using only low parts");
+STATISTIC(MUXHIGHs, "Number of Muxes using only high parts");
+STATISTIC(MUXHILOs, "Number of Muxes using high and low parts");
+STATISTIC(BADMUXs, "Number of Muxes ending up in illegal registers");
+
+namespace llvm {
+  void initializeSystemZSelectMuxPass(PassRegistry&);
+}
+
+namespace {
+class SystemZSelectMux : public MachineFunctionPass {
+public:
+  static char ID;
+  SystemZSelectMux() : MachineFunctionPass(ID) {
+    initializeSystemZSelectMuxPass(*PassRegistry::getPassRegistry());
+  }
+
+  const SystemZInstrInfo *TII;
+  const TargetRegisterInfo *TRI;
+  SlotIndexes *SI;
+
+  bool runOnMachineFunction(MachineFunction &Fn) override;
+
+  StringRef getPassName() const override { return SYSTEMZ_EXPAND_PSEUDO_NAME; }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addUsedIfAvailable<SlotIndexes>();
+    AU.addPreserved<SlotIndexes>();
+    AU.addPreserved<LiveStacks>();
+    AU.setPreservesCFG();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
+private:
+  bool selectMBB(MachineBasicBlock &MBB);
+  bool selectMI(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
+                MachineBasicBlock::iterator &NextMBBI);
+};
+char SystemZSelectMux::ID = 0;
+}
+
+INITIALIZE_PASS(SystemZSelectMux, "systemz-select-mux",
+                SYSTEMZ_EXPAND_PSEUDO_NAME, false, false)
+
+/// Returns an instance of the Select Mux pass.
+FunctionPass *llvm::createSystemZSelectMuxPass(SystemZTargetMachine &TM) {
+  return new SystemZSelectMux();
+}
+
+/// If MBBI references a pseudo instruction that should be selected here,
+/// do it and return true.  Otherwise return false.
+bool SystemZSelectMux::selectMI(MachineBasicBlock &MBB,
+                                MachineBasicBlock::iterator MBBI,
+                                MachineBasicBlock::iterator &NextMBBI) {
+  MachineInstr &MI = *MBBI;
+  unsigned Opcode = MI.getOpcode();
+  switch (Opcode) {
+  case SystemZ::LOCRMux: {
+    SystemZII::MuxInfo MuxI(MI, TRI);
+    if (MuxI.isLOW(0) && MuxI.isLOW(2))
+      MI.setDesc(TII->get(SystemZ::LOCR));
+    else if (MuxI.isHIGH(0) && MuxI.isHIGH(2))
+      MI.setDesc(TII->get(SystemZ::LOCFHR));
+    else {
+      // If we were unable to implement the pseudo with a single instruction,
+      // we need to convert it back into a branch sequence.  This cannot be
+      // done here since the caller of expandPostRAPseudo does not handle
+      // changes to the CFG correctly.  This change is defered to the
+      // SystemZExpandPseudo pass.
+      LOCRMuxJumps++;
+      return false;
+    }
+    LOCRs++;
+    return true;
+  }
+
+  case SystemZ::CHIMux: {
+    bool IsHigh = SystemZ::GRH32BitRegClass.contains(MI.getOperand(0).getReg());
+    MI.setDesc(TII->get(IsHigh ? SystemZ::CIH :SystemZ::CHI));
+    return true;
+  }
+
+  case SystemZ::CFIMux: {
+    bool IsHigh = SystemZ::GRH32BitRegClass.contains(MI.getOperand(0).getReg());
+    MI.setDesc(TII->get(IsHigh ? SystemZ::CIH :SystemZ::CFI));
+    return true;
+  }
+
+  case SystemZ::CRMux:
+  case SystemZ::CLRMux: {
+    // MI is a 32 bit compare with register pseudo instruction. Replace it
+    // with one of the three possible opcodes. "LowHi" is not supported and
+    // must therefore be swapped (in SystemZExpandPseudo.cpp).
+    bool Legal = true;
+    SystemZII::MuxInfo MuxI(MI, TRI);
+    if (MuxI.isLOW(0) && MuxI.isLOW(1))
+      MUXLOWs++;
+    else if (MuxI.isHIGH(0) && MuxI.isHIGH(1))
+      MUXHIGHs++;
+    else if (MuxI.isHIGH(0) && MuxI.isLOW(1))
+      MUXHILOs++;
+    else { // LowHi
+      BADMUXs++;
+      Legal = false;
+    }
+    bool Success = MuxI.selectCmpMux(TII);
+    assert(Legal == Success && "MuxInfo broken?");
+    return Success;
+  }
+
+  case SystemZ::ARMux:
+  case SystemZ::ARMuxK:
+  case SystemZ::ALRMux:
+  case SystemZ::ALRMuxK:
+  case SystemZ::SRMux:
+  case SystemZ::SRMuxK:
+  case SystemZ::SLRMux:
+  case SystemZ::SLRMuxK: {
+    unsigned OldBadMuxStat = BADMUXs;
+    SystemZII::MuxInfo MuxI(MI, TRI);
+    if (MuxI.isLOW(0) && MuxI.isLOW(1) && MuxI.isLOW(2))
+      MUXLOWs++;
+    else if (MuxI.isHIGH(0) && MuxI.isHIGH(1) && MuxI.isHIGH(2))
+      MUXHIGHs++;
+    else if (MuxI.isHIGH(0) && (MuxI.isHIGH(1) || MuxI.isHIGH(2))) {
+      if (MuxI.isHIGH(2)) { // HLH is unsupported.
+        if (MuxI.isAdd(TII)) {
+          MuxI.commute(TII);
+          MUXHILOs++;
+        }
+        else
+          BADMUXs++;
+      } else
+        MUXHILOs++;
+    }
+    else
+      BADMUXs++;
+
+    bool Success = MuxI.selectAddSubMux(TII, SI);
+    assert(Success == (OldBadMuxStat == BADMUXs) && "MuxInfo broken?");
+    return Success;
+  }
+
+  default:
+    break;
+  }
+
+  return false;
+}
+
+/// Iterate over the instructions in basic block MBB and select any
+/// pseudo instructions.  Return true if anything was modified.
+bool SystemZSelectMux::selectMBB(MachineBasicBlock &MBB) {
+  bool Modified = false;
+
+  MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
+  while (MBBI != E) {
+    MachineBasicBlock::iterator NMBBI = std::next(MBBI);
+    Modified |= selectMI(MBB, MBBI, NMBBI);
+    MBBI = NMBBI;
+  }
+
+  return Modified;
+}
+
+bool SystemZSelectMux::runOnMachineFunction(MachineFunction &MF) {
+  TII = static_cast<const SystemZInstrInfo *>(MF.getSubtarget().getInstrInfo());
+  SI = getAnalysisIfAvailable<SlotIndexes>();
+  TRI = MF.getSubtarget<SystemZSubtarget>().getRegisterInfo();
+
+  bool Modified = false;
+  for (auto &MBB : MF)
+    Modified |= selectMBB(MBB);
+  return Modified;
+}
+

lib/Target/SystemZ/SystemZTargetMachine.cpp

createPostMachineScheduler(MachineSchedContext *C) const override {
     return new ScheduleDAGMI(C,
                              llvm::make_unique<SystemZPostRASchedStrategy>(C),
                              /*RemoveKillFlags=*/true);
   }
 
   void addIRPasses() override;
   bool addInstSelector() override;
   bool addILPOpts() override;
+  void addPostRewrite() override;
   void addPreSched2() override;
   void addPreEmitPass() override;
 };
 
 } // end anonymous namespace
 
 void SystemZPassConfig::addIRPasses() {
   if (getOptLevel() != CodeGenOpt::None) {
if (getOptLevel() != CodeGenOpt::None)
   return false;
 }
 
 bool SystemZPassConfig::addILPOpts() {
   addPass(&EarlyIfConverterID);
   return true;
 }
 
+void SystemZPassConfig::addPostRewrite() {
+  addPass(createSystemZSelectMuxPass(getSystemZTargetMachine()));
+}
+
 void SystemZPassConfig::addPreSched2() {
+  // This is added in addPostRewrite() when RAGreedy is run (at -O1 and above).
+  if (getOptLevel() == CodeGenOpt::None)
+    addPass(createSystemZSelectMuxPass(getSystemZTargetMachine()));
+
   addPass(createSystemZExpandPseudoPass(getSystemZTargetMachine()));
 
   if (getOptLevel() != CodeGenOpt::None)
     addPass(&IfConverterID);
 }
 
 void SystemZPassConfig::addPreEmitPass() {
   // Do instruction shortening before compare elimination because some

lib/Target/X86/X86InstrInfo.h

public:
   /// specified operand(s).  If this is possible, the target should perform the
   /// folding and return true, otherwise it should return false.  If it folds
   /// the instruction, it is likely that the MachineInstruction the iterator
   /// references has been changed.
   MachineInstr *
   foldMemoryOperandImpl(MachineFunction &MF, MachineInstr &MI,
                         ArrayRef<unsigned> Ops,
                         MachineBasicBlock::iterator InsertPt, int FrameIndex,
-                        LiveIntervals *LIS = nullptr) const override;
+                        LiveIntervals *LIS = nullptr,
+                        VirtRegMap *VRM = nullptr) const override;
 
   /// foldMemoryOperand - Same as the previous version except it allows folding
   /// of any load and store from / to any address, not just from a specific
   /// stack slot.
   MachineInstr *foldMemoryOperandImpl(
       MachineFunction &MF, MachineInstr &MI, ArrayRef<unsigned> Ops,
       MachineBasicBlock::iterator InsertPt, MachineInstr &LoadMI,
       LiveIntervals *LIS = nullptr) const override;

lib/Target/X86/X86InstrInfo.cpp

if (PrintFailedFusing && !MI.isCopy())
     dbgs() << "We failed to fuse operand " << OpNum << " in " << MI;
   return nullptr;
 }
 
 MachineInstr *
 X86InstrInfo::foldMemoryOperandImpl(MachineFunction &MF, MachineInstr &MI,
                                     ArrayRef<unsigned> Ops,
                                     MachineBasicBlock::iterator InsertPt,
-                                    int FrameIndex, LiveIntervals *LIS) const {
+                                    int FrameIndex, LiveIntervals *LIS,
+                                    VirtRegMap *VRM) const {
   // Check switch flag
   if (NoFusing)
     return nullptr;
 
   // Avoid partial and undef register update stalls unless optimizing for size.
   if (!MF.getFunction().optForSize() &&
       (hasPartialRegUpdate(MI.getOpcode(), Subtarget, /*ForLoadFold*/true) ||
        shouldPreventUndefRegUpdateMemFold(MF, MI)))

test/CodeGen/SystemZ/debuginstr-00.mir

frameInfo:
   maxCallFrameSize: 0
 body:             |
   bb.0.bb:
     renamable $r0l = LHIMux 0
   
   bb.1.bb2:
     liveins: $r0l
   
-    CHIMux renamable $r0l, 0, implicit-def $cc
+    CHI renamable $r0l, 0, implicit-def $cc
     BRC 14, 6, %bb.1, implicit killed $cc
   
   bb.2.bb3.preheader:
     liveins: $r0l
   
     renamable $r1d = LGHI 2
   
   bb.3.bb3:

test/CodeGen/SystemZ/expand-mux-pseudos.mir

+# RUN: llc -mtriple=s390x-linux-gnu -mcpu=z13 -start-after=postrapseudos \
+# RUN:   -verify-machineinstrs -enable-post-misched=false %s -o - | FileCheck %s
+#
+# Test that SystemZExpandPseudo can handle all combinations of high/low
+# registers and transform all Add / Sub Mux instructions into legal target
+# instructions.
+
+name:            fun0
+body:             |
+  bb.0:
+    successors: %bb.1
+    $r0l = LHI 0
+    $r0h = IIHF 0
+    $r1l = LHI 0
+    $r1h = IIHF 0
+    $r2l = LHI 0
+    $r2h = IIHF 0
+
+    ; CHECK-LABEL: fun0
+    ; CHECK:      llihl   %r2, 0
+
+    ;; ARMuxK
+
+    ; LLL
+    renamable $r2l = ARMuxK renamable $r1l, renamable $r0l, implicit-def dead $cc
+      ; CHECK-NEXT:     ark     %r2, %r1, %r0
+    renamable $r2l = ARMuxK renamable $r2l, renamable $r0l, implicit-def dead $cc
+      ; CHECK-NEXT:     ar      %r2, %r0
+
+    ; LLH
+    renamable $r2l = ARMuxK renamable $r1l, renamable $r1h, implicit-def dead $cc
+      ; CHECK-NEXT:     risblg  %r2, %r1, 0, 159, 32
+      ; CHECK-NEXT:     ark     %r2, %r1, %r2
+    renamable $r2l = ARMuxK renamable $r2l, renamable $r1h, implicit-def dead $cc
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+      ; CHECK-NEXT:   ahhhr %r2, %r2, %r1
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+    renamable $r2l = ARMuxK renamable $r2l, renamable $r2h, implicit-def dead $cc
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+      ; CHECK-NEXT:   ahhlr %r2, %r2, %r2
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+
+    ; LHL
+    renamable $r2l = ARMuxK renamable $r1h, renamable $r1l, implicit-def dead $cc
+      ; CHECK-NEXT:   risblg  %r2, %r1, 0, 159, 32
+      ; CHECK-NEXT:   ar  %r2, %r1
+    renamable $r2l = ARMuxK renamable $r1h, renamable $r2l, implicit-def dead $cc
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+      ; CHECK-NEXT:   ahhhr %r2, %r1, %r2
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+    renamable $r2l = ARMuxK renamable $r2h, renamable $r2l, implicit-def dead $cc
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+      ; CHECK-NEXT:   ahhlr %r2, %r2, %r2
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+
+    ; LHH
+    renamable $r2l = ARMuxK renamable $r1h, renamable $r0h, implicit-def dead $cc
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+      ; CHECK-NEXT:   ahhhr %r2, %r1, %r0
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+    renamable $r2l = ARMuxK renamable $r2h, renamable $r0h, implicit-def dead $cc
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+      ; CHECK-NEXT:   risbhg  %r2, %r2, 0, 159, 32
+      ; CHECK-NEXT:   ahhhr %r2, %r2, %r0
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+    renamable $r2l = ARMuxK renamable $r0h, renamable $r2h, implicit-def dead $cc
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+      ; CHECK-NEXT:   ahhlr %r2, %r0, %r2
+      ; CHECK-NEXT:   rllg  %r2, %r2, 32
+    renamable $r2l = ARMuxK renamable $r2h, renamable $r2h, implicit-def dead $cc
+      ; CHECK-NEXT:   risblg  %r2, %r2, 0, 159, 32
+      ; CHECK-NEXT: ar  %r2, %r2
+
+    ; HLL
+    renamable $r2h = ARMuxK renamable $r1l, renamable $r0l, implicit-def dead $cc
+      ; CHECK-NEXT: risbhg  %r2, %r1, 0, 159, 32
+      ; CHECK-NEXT: ahhlr %r2, %r2, %r0
+    renamable $r2h = ARMuxK renamable $r1l, renamable $r1l, implicit-def dead $cc
+      ; CHECK-NEXT: risbhg  %r2, %r1, 0, 159, 32
+      ; CHECK-NEXT: ahhhr %r2, %r2, %r2
+
+    ; HLH
+    renamable $r2h = ARMuxK renamable $r1l, renamable $r0h, implicit-def dead $cc
+      ; CHECK-NEXT: ahhlr %r2, %r0, %r1
+    renamable $r2h = ARMuxK renamable $r1l, renamable $r2h, implicit-def dead $cc
+      ; CHECK-NEXT: ahhlr %r2, %r2, %r1
+    renamable $r2h = ARMuxK renamable $r2l, renamable $r2h, implicit-def dead $cc
+      ; CHECK-NEXT: ahhlr %r2, %r2, %r2
+
+    ; HHL
+    renamable $r2h = ARMuxK renamable $r1h, renamable $r1l, implicit-def dead $cc
+      ; CHECK-NEXT: ahhlr %r2, %r1, %r1
+    ; HHH
+    renamable $r2h = ARMuxK renamable $r1h, renamable $r0h, implicit-def dead $cc
+      ; CHECK-NEXT: ahhhr %r2, %r1, %r0
+
+    ;; SRMuxK
+
+    ; LLL
+    renamable $r2l = SRMuxK renamable $r1l, renamable $r0l, implicit-def dead $cc
+      ; CHECK-NEXT: srk %r2, %r1, %r0
+    renamable $r2l = SRMuxK renamable $r2l, renamable $r0l, implicit-def dead $cc
+      ; CHECK-NEXT: sr  %r2, %r0
+
+    ; LLH
+    renamable $r2l = SRMuxK renamable $r1l, renamable $r1h, implicit-def dead $cc
+      ; CHECK-NEXT: risblg  %r2, %r1, 0, 159, 32
+      ; CHECK-NEXT: srk %r2, %r1, %r2
+    renamable $r2l = SRMuxK renamable $r2l, renamable $r1h, implicit-def dead $cc
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+      ; CHECK-NEXT: shhhr %r2, %r2, %r1
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+    renamable $r2l = SRMuxK renamable $r2l, renamable $r2h, implicit-def dead $cc
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+      ; CHECK-NEXT: shhlr %r2, %r2, %r2
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+
+    ; LHL
+    renamable $r2l = SRMuxK renamable $r1h, renamable $r1l, implicit-def dead $cc
+      ; CHECK-NEXT: risblg  %r2, %r1, 0, 159, 32
+      ; CHECK-NEXT: sr  %r2, %r1
+    renamable $r2l = SRMuxK renamable $r1h, renamable $r2l, implicit-def dead $cc
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+      ; CHECK-NEXT: shhhr %r2, %r1, %r2
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+    renamable $r2l = SRMuxK renamable $r2h, renamable $r2l, implicit-def dead $cc
+      ; CHECK-NEXT: lnr %r2, %r2
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+      ; CHECK-NEXT: ahhlr %r2, %r2, %r2
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+
+    ; LHH
+    renamable $r2l = SRMuxK renamable $r1h, renamable $r0h, implicit-def dead $cc
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+      ; CHECK-NEXT: shhhr %r2, %r1, %r0
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+    renamable $r2l = SRMuxK renamable $r2h, renamable $r0h, implicit-def dead $cc
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+      ; CHECK-NEXT: risbhg  %r2, %r2, 0, 159, 32
+      ; CHECK-NEXT: shhhr %r2, %r2, %r0
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+    renamable $r2l = SRMuxK renamable $r0h, renamable $r2h, implicit-def dead $cc
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+      ; CHECK-NEXT: shhlr %r2, %r0, %r2
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+    renamable $r2l = SRMuxK renamable $r2h, renamable $r2h, implicit-def dead $cc
+      ; CHECK-NEXT: risblg  %r2, %r2, 0, 159, 32
+      ; CHECK-NEXT: sr  %r2, %r2
+
+    ; HLL
+    renamable $r2h = SRMuxK renamable $r1l, renamable $r0l, implicit-def dead $cc
+      ; CHECK-NEXT: risbhg  %r2, %r1, 0, 159, 32
+      ; CHECK-NEXT: shhlr %r2, %r2, %r0
+    renamable $r2h = SRMuxK renamable $r1l, renamable $r1l, implicit-def dead $cc
+      ; CHECK-NEXT: risbhg  %r2, %r1, 0, 159, 32
+      ; CHECK-NEXT: shhhr %r2, %r2, %r2
+
+    ; HLH
+    renamable $r2h = SRMuxK renamable $r1l, renamable $r0h, implicit-def dead $cc
+      ; CHECK-NEXT: risbhg  %r2, %r1, 0, 159, 32
+      ; CHECK-NEXT: shhhr %r2, %r2, %r0
+    renamable $r2h = SRMuxK renamable $r1l, renamable $r2h, implicit-def dead $cc
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+      ; CHECK-NEXT: srk %r2, %r1, %r2
+      ; CHECK-NEXT: rllg  %r2, %r2, 32
+    renamable $r2h = SRMuxK renamable $r2l, renamable $r2h, implicit-def dead $cc
+      ; CHECK-NEXT: xihf  %r2, 4294967295
+      ; CHECK-NEXT: aih %r2, 1
+      ; CHECK-NEXT: ahhlr %r2, %r2, %r2
+
+    ; HHL
+    renamable $r2h = SRMuxK renamable $r1h, renamable $r1l, implicit-def dead $cc
+      ; CHECK-NEXT: shhlr %r2, %r1, %r1
+
+    ; HHH
+    renamable $r2h = SRMuxK renamable $r1h, renamable $r0h, implicit-def dead $cc
+      ; CHECK-NEXT: shhhr %r2, %r1, %r0
+
+  bb.1:
+    successors: 
+
+...
+
+# Test comparisons.
+
+---
+name:             fun1
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    successors: %bb.1, %bb.2
+    $r0l = LHI 0
+    $r0h = IIHF 0
+    $r1l = LHI 0
+    $r1h = IIHF 0
+    $r2l = LHI 0
+    $r2h = IIHF 0
+
+    ; CHECK-LABEL: fun1
+    ; CHECK:      iihf   %r2, 0
+
+    CRMux renamable $r1l, renamable $r2l, implicit-def $cc
+    BRC 14, 4, %bb.2, implicit killed $cc
+      ; CHECK-NEXT: crjl  %r1, %r2, .LBB1_2
+
+  bb.1:
+    successors:
+    $r0l = LHI 0
+
+  bb.2:
+    successors: %bb.3, %bb.4
+    liveins: $r1h, $r2l
+
+    CRMux renamable $r1h, renamable $r2l, implicit-def $cc
+    BRC 14, 4, %bb.4, implicit killed $cc
+      ; CHECK-LABEL:    .LBB1_2:
+      ; CHECK-NEXT: chlr  %r1, %r2
+      ; CHECK-NEXT: jl  .LBB1_4
+
+  bb.3:
+    successors: 
+    $r0l = LHI 0
+
+  bb.4:
+    successors: %bb.5, %bb.6
+    liveins: $r1h, $r2h
+
+    CRMux renamable $r1h, renamable $r2h, implicit-def $cc
+    BRC 14, 4, %bb.6, implicit killed $cc
+      ; CHECK-LABEL:    .LBB1_4:
+      ; CHECK-NEXT: chhr  %r1, %r2
+      ; CHECK-NEXT: jl  .LBB1_6
+
+  bb.5:
+    successors: 
+    $r0l = LHI 0
+
+  bb.6:
+    successors: %bb.7, %bb.8
+    liveins: $r1l, $r2h
+
+    CRMux renamable $r1l, renamable $r2h, implicit-def $cc
+    BRC 14, 4, %bb.8, implicit killed $cc
+      ; CHECK-LABEL:    .LBB1_6:
+      ; CHECK-NEXT: chlr  %r2, %r1
+      ; CHECK-NEXT: jh  .LBB1_8
+
+  bb.7:
+    successors: 
+    $r0l = LHI 0
+
+  bb.8:
+    liveins: $r1l, $r2h
+
+    CRMux renamable $r1l, renamable $r2h, implicit-def $cc
+      ; CHECK-LABEL:    .LBB1_8:
+      ; CHECK-NEXT: rllg  %r1, %r1, 32
+      ; CHECK-NEXT: chhr  %r1, %r2
+      ; CHECK-NEXT: rllg  %r1, %r1, 32
+      ; CHECK-NEXT: jl  .LBB1_10
+
+  bb.9:
+    successors: %bb.10, %bb.11
+    liveins: $cc
+    BRC 14, 4, %bb.11, implicit killed $cc
+
+  bb.10:
+    successors: 
+    $r0l = LHI 0
+
+  bb.11:
+    successors: %bb.12, %bb.13
+    liveins: $r1l, $r1h, $r2l
+
+    CRMux renamable $r1h, renamable $r2l, implicit-def $cc
+    renamable $r1l = LOCHI killed renamable $r1l, 0, 14, 8, implicit $cc
+    BRC 14, 4, %bb.13, implicit killed $cc
+      ; CHECK-LABEL:    .LBB1_10:
+      ; CHECK-NEXT: chlr  %r1, %r2
+      ; CHECK-NEXT: lochie  %r1, 0
+      ; CHECK-NEXT: jl  .LBB1_12
+
+  bb.12:
+    successors: 
+    $r0l = LHI 0
+
+  bb.13:
+    successors: %bb.14, %bb.15
+    liveins: $r1l, $r1h, $r2l
+
+    CRMux renamable $r2l, renamable $r1h, implicit-def $cc
+    renamable $r1l = LOCHI killed renamable $r1l, 0, 14, 8, implicit $cc
+    BRC 14, 4, %bb.15, implicit killed $cc
+      ; CHECK-LABEL:    .LBB1_12:
+      ; CHECK-NEXT: chlr  %r1, %r2
+      ; CHECK-NEXT: lochie  %r1, 0
+      ; CHECK-NEXT: jh  .LBB1_14
+
+  bb.14:
+    successors: 
+    $r0l = LHI 0
+
+  bb.15:
+
+...