Regenerate removed implicit defs in BranchFolder where necessary

[kparzysz]

Summary

Branch folder removes implicit defs if they are the only non-branching instructions in a block, and the branches do not use the defined registers. The problem is that in some cases these implicit defs are required for the liveness information to be correct.
After branch optimizations, regenerate those implicit defs that are still necessary.

[MatzeB]

Hmm BranchFolder::OptimizeImpDefsBlock() has some odd logic indeed, I wonder why nobody found problems with it earlier.

The patch is slightly odd as well. BranchFolder::RegenerateImpDefsInBlock() should be able to restore any missing IMPLICIT_DEFS, so I am not sure why that global set of registers is kept. This also makes me feel uneasy, the approach does not target blocks where IMPLICIT_DEFS were removed (or rather their new predecessors in case they got merged), but instead attempts to fix up any block. (The entry in the ImpDefRegs set may come from a completely different basic block). Nonetheless given that this appears to be broken right now I would not be opposed to the patch when some of the points below are addressed:

lib/CodeGen/BranchFolding.cpp

160

What was wrong with SmallSet? SmallSet is usually the better choice over std::set because it provides inline storage and I would consider a small number of elements likely here. Also std::set is ordered and therefore usually not implemented with more efficient hashing.

167–169

Maybe only put "Reg" into the set. And instead does some TRI.regsOerlap() test in the 2nd loop. This may be slightly more efficient anyway as I would expect the tupical unconditional branch has no inputs so there is nothing to test. But the real benefit would be to not have all those subregs in the ImpDefRegs set later.

200–202

This should probably not be restricted to physregs. The pass description claims that the pass should also work with virtual regs. (NVPTX and WebAsm are still using virtual registers late in the codegen pipeline).

215

Using stepForward is discouraged. It will result in overly conservative liveness in case of missing kill flags. If possible go for stepBackward().

Proposal for a different strategy:
Collect live out regs, make a copy of that set
check each instruction backwards:

check operands:
    on reg define: remove reg from the copy set
    on reg kill: check if reg is still in the copy set, if so append IMPLICIT_DEF at the end
simulate liveness on the normal set

when reaching the beginning compare liveregs with liveins, for missing regs add IMPLICIT_DEF instruction.

275

SmallSet?

302

All of this can be skipped if ImpDefRegs.empty() or MachineRegisterInfo::tracksLiveness() returns false.

[kparzysz]

In D25370#565130, @MatzeB wrote:

Hmm BranchFolder::OptimizeImpDefsBlock() has some odd logic indeed, I wonder why nobody found problems with it earlier.

The patch is slightly odd as well. BranchFolder::RegenerateImpDefsInBlock() should be able to restore any missing IMPLICIT_DEFS, so I am not sure why that global set of registers is kept.

It didn't start that way, but in some Thumb testcase it produced an implicit def of LR, which caused some CHECK-NEXT line to fail (implicit defs show up in comments in the final assembly). I thought LR would be reserved on ARM, but it's not (apparently deliberately) and I didn't want to touch anything there. That is really the only motivation for this global set.

This also makes me feel uneasy, the approach does not target blocks where IMPLICIT_DEFS were removed (or rather their new predecessors in case they got merged), but instead attempts to fix up any block.

The reason is that the anticipated optimizations could do just about anything with the rest of the code: merge block, split blocks, duplicate, etc. I thought that keeping track of what happened to what block would be too convoluted and too error-prone.

lib/CodeGen/BranchFolding.cpp

160

SmallSet does not provide iterators: that was the reason I used set.

200–202

I use LivePhysRegs to establish available registers. It does not work with virtual registers.

[kparzysz]

[MatzeB]

In D25370#565145, @kparzysz wrote:

In D25370#565130, @MatzeB wrote:

Hmm BranchFolder::OptimizeImpDefsBlock() has some odd logic indeed, I wonder why nobody found problems with it earlier.

The patch is slightly odd as well. BranchFolder::RegenerateImpDefsInBlock() should be able to restore any missing IMPLICIT_DEFS, so I am not sure why that global set of registers is kept.

It didn't start that way, but in some Thumb testcase it produced an implicit def of LR, which caused some CHECK-NEXT line to fail (implicit defs show up in comments in the final assembly). I thought LR would be reserved on ARM, but it's not (apparently deliberately) and I didn't want to touch anything there. That is really the only motivation for this global set.

A register may be non-allocatable but still not reserved, we do track liveness for those registers.
This seems like an example for the reservations I had: Was the pass cleaning up something that was broken before anyway which I maybe should have left alone? Was the IMPLICIT_DEF in that case legit so we should rather adjust the CHECKs. Having a global set seems like a bad idea to restrict this maybe a legit IMPLICIT_DEF of LR was removed in another block...

This also makes me feel uneasy, the approach does not target blocks where IMPLICIT_DEFS were removed (or rather their new predecessors in case they got merged), but instead attempts to fix up any block.

The reason is that the anticipated optimizations could do just about anything with the rest of the code: merge block, split blocks, duplicate, etc. I thought that keeping track of what happened to what block would be too convoluted and too error-prone.

I understand but it doesn't convince me that the course taken is a good one :)

lib/CodeGen/BranchFolding.cpp

160

Bummer. LLVM also features DensetSet which I would still consider a better choice than std::set here where we don't need a stable order.

200–202

I just realized that block live in lists only contain PhysRegs right now. NVPTX and WebAsm both seem to have liveness tracking disabled past regalloc. So the physreg check can be an assert() instead.

[kparzysz]

There is a better plan: D25478.

[kparzysz]

I want to abandon this patch. I don't think there is a good way of making this work without some form of liveness analysis.

[MatzeB]

This comment was removed by MatzeB.

lib/CodeGen/BranchFolding.h

 //===-- BranchFolding.h - Fold machine code branch instructions -*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_CODEGEN_BRANCHFOLDING_H
 #define LLVM_LIB_CODEGEN_BRANCHFOLDING_H
 
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/Support/BlockFrequency.h"
+#include <set>
 #include <vector>
 
 namespace llvm {
   class MachineBlockFrequencyInfo;
   class MachineBranchProbabilityInfo;
   class MachineFunction;
   class MachineModuleInfo;
   class MachineLoopInfo;
private:
     bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
                                    MachineBasicBlock *SuccBB,
                                    unsigned maxCommonTailLength,
                                    unsigned &commonTailIndex);
 
     bool OptimizeBranches(MachineFunction &MF);
     bool OptimizeBlock(MachineBasicBlock *MBB);
     void RemoveDeadBlock(MachineBasicBlock *MBB);
-    bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
+    bool PurgeImpDefsInBlock(MachineBasicBlock *MBB,
+                             std::set<MCPhysReg> &ImpDefRegs);
+    bool RegenerateImpDefsInBlock(MachineBasicBlock *MBB,
+                                  std::set<MCPhysReg> &ImpDefRegs);
 
     bool HoistCommonCode(MachineFunction &MF);
     bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
   };
 }
 
 #endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */

lib/CodeGen/BranchFolding.cpp

 #include "BranchFolding.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/Function.h"

 /// followed by terminators, and if the implicitly defined registers are not
 /// used by the terminators, remove those implicit_def's. e.g.
 /// BB1:
 ///   r0 = implicit_def
 ///   r1 = implicit_def
 ///   br
 /// This block can be optimized away later if the implicit instructions are
 /// removed.
-bool BranchFolder::OptimizeImpDefsBlock(MachineBasicBlock *MBB) {
-  SmallSet<unsigned, 4> ImpDefRegs;
+bool BranchFolder::PurgeImpDefsInBlock(MachineBasicBlock *MBB,
+                                       std::set<MCPhysReg> &ImpDefRegs) {
+  std::set<unsigned> LocalImpDefRegs;
   MachineBasicBlock::iterator I = MBB->begin();
   while (I != MBB->end()) {
     if (!I->isImplicitDef())
       break;
     unsigned Reg = I->getOperand(0).getReg();
     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
       for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
            SubRegs.isValid(); ++SubRegs)
-        ImpDefRegs.insert(*SubRegs);
+        LocalImpDefRegs.insert(*SubRegs);
     } else {
-      ImpDefRegs.insert(Reg);
+      LocalImpDefRegs.insert(Reg);
     }
     ++I;
   }
-  if (ImpDefRegs.empty())
+  if (LocalImpDefRegs.empty())
     return false;
 
   MachineBasicBlock::iterator FirstTerm = I;
   while (I != MBB->end()) {
     if (!TII->isUnpredicatedTerminator(*I))
       return false;
     // See if it uses any of the implicitly defined registers.
     for (const MachineOperand &MO : I->operands()) {
       if (!MO.isReg() || !MO.isUse())
         continue;
       unsigned Reg = MO.getReg();
-      if (ImpDefRegs.count(Reg))
+      if (LocalImpDefRegs.count(Reg))
         return false;
     }
     ++I;
   }
 
   I = MBB->begin();
   while (I != FirstTerm) {
     MachineInstr *ImpDefMI = &*I;
     ++I;
     MBB->erase(ImpDefMI);
   }
 
+  for (unsigned Reg : LocalImpDefRegs)
+    if (TargetRegisterInfo::isPhysicalRegister(Reg))
+      ImpDefRegs.insert(Reg);
+
+  return true;
+}
+
+bool BranchFolder::RegenerateImpDefsInBlock(MachineBasicBlock *MBB,
+                                            std::set<MCPhysReg> &ImpDefRegs) {
+  SmallVector<std::pair<unsigned, const MachineOperand*>,8> Tmp;
+  MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
+
+  LiveRegs.init(TRI);
+  LiveRegs.addLiveIns(*MBB);
+  for (MachineInstr &MI : *MBB)
+    LiveRegs.stepForward(MI, Tmp);
+
+  LivePhysRegs LiveOut(TRI);
+  LiveOut.addLiveOutsNoPristines(*MBB);
+
+  auto HasSuperInSet = [this] (unsigned Reg, bool Self, LivePhysRegs &LPR) {
+    for (MCSuperRegIterator S(Reg, TRI, Self); S.isValid(); ++S)
+      if (LPR.contains(*S))
         return true;
+    return false;
+  };
+
+  // LivePhysRegs always adds/removes all subregisters of a given register.
+  // Create a set of "largest" registers, i.e. registers that have no super
+  // register also in the set.
+  std::set<MCPhysReg> NeedLiveOut;
+  for (MCPhysReg Reg : LiveOut) {
+    if (HasSuperInSet(Reg, false, LiveOut))
+      continue;
+    if (MRI.isReserved(Reg) || !ImpDefRegs.count(Reg))
+      continue;
+    NeedLiveOut.insert(Reg);
+  }
+
+  bool Changed = false;
+  MachineBasicBlock::iterator Term = MBB->getFirstTerminator();
+  DebugLoc DL = MBB->findDebugLoc(Term);
+  for (MCPhysReg Reg : NeedLiveOut) {
+    if (HasSuperInSet(Reg, true, LiveRegs))
+      continue;
+    BuildMI(*MBB, Term, DL, TII->get(TargetOpcode::IMPLICIT_DEF), Reg);
+    Changed = true;
+  }
+
+  return Changed;
 }
 
 /// OptimizeFunction - Perhaps branch folding, tail merging and other
 /// CFG optimizations on the given function.  Block placement changes the layout
 /// and may create new tail merging opportunities.
 bool BranchFolder::OptimizeFunction(MachineFunction &MF,
                                     const TargetInstrInfo *tii,
                                     const TargetRegisterInfo *tri,
bool BranchFolder::OptimizeFunction(MachineFunction &MF,
   MMI = mmi;
   MLI = mli;
 
   MachineRegisterInfo &MRI = MF.getRegInfo();
   UpdateLiveIns = MRI.tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF);
   if (!UpdateLiveIns)
     MRI.invalidateLiveness();
 
+  std::set<MCPhysReg> ImpDefRegs;
+
   // Fix CFG.  The later algorithms expect it to be right.
   bool MadeChange = false;
   for (MachineBasicBlock &MBB : MF) {
     MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
     SmallVector<MachineOperand, 4> Cond;
     if (!TII->analyzeBranch(MBB, TBB, FBB, Cond, true))
       MadeChange |= MBB.CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
-    MadeChange |= OptimizeImpDefsBlock(&MBB);
+    MadeChange |= PurgeImpDefsInBlock(&MBB, ImpDefRegs);
   }
 
   // Recalculate funclet membership.
   FuncletMembership = getFuncletMembership(MF);
 
   bool MadeChangeThisIteration = true;
   while (MadeChangeThisIteration) {
     MadeChangeThisIteration    = TailMergeBlocks(MF);
     // No need to clean up if tail merging does not change anything after the
     // block placement.
     if (!AfterBlockPlacement || MadeChangeThisIteration)
       MadeChangeThisIteration |= OptimizeBranches(MF);
     if (EnableHoistCommonCode)
       MadeChangeThisIteration |= HoistCommonCode(MF);
     MadeChange |= MadeChangeThisIteration;
   }
 
+  for (MachineBasicBlock &MBB : MF)
+    MadeChange |= RegenerateImpDefsInBlock(&MBB, ImpDefRegs);
+
   // See if any jump tables have become dead as the code generator
   // did its thing.
   MachineJumpTableInfo *JTI = MF.getJumpTableInfo();
   if (!JTI)
     return MadeChange;
 
   // Walk the function to find jump tables that are live.
   BitVector JTIsLive(JTI->getJumpTables().size());

test/CodeGen/Hexagon/branchfolder-keep-impdef.ll

+; RUN: llc -march=hexagon -verify-machineinstrs < %s | FileCheck %s
+;
+; Check that the testcase compiles successfully. Expect that if-conversion
+; took place.
+; CHECK-LABEL: fred:
+; CHECK: if (!p0) r1 = memw(r0 + #0)
+
+target triple = "hexagon"
+
+define void @fred(i32 %p0) local_unnamed_addr align 2 {
+b0:
+  br i1 undef, label %b1, label %b2
+
+b1:                                               ; preds = %b0
+  %t0 = load i8*, i8** undef, align 4
+  br label %b2
+
+b2:                                               ; preds = %b1, %b0
+  %t1 = phi i8* [ %t0, %b1 ], [ undef, %b0 ]
+  %t2 = getelementptr inbounds i8, i8* %t1, i32 %p0
+  tail call void @llvm.memmove.p0i8.p0i8.i32(i8* undef, i8* %t2, i32 undef, i32 1, i1 false) #1
+  unreachable
+}
+
+declare void @llvm.memmove.p0i8.p0i8.i32(i8* nocapture, i8* nocapture readonly, i32, i32, i1) #0
+
+attributes #0 = { argmemonly nounwind }
+attributes #1 = { nounwind }
+