[BOLT] ZeroIdiom pass

[Amir]

Add test

[Amir]

Test failing with initial version: https://paste.debian.net/1279337/
Test passing with this version: https://paste.debian.net/1279338/
Clang passing with this version: https://paste.debian.net/1279339/

[Amir]

Only return true from replaceZeroIdiom if the replacement was performed

[Amir]

Remove the use of CG

[Amir]

Add knob

[Amir]

Don't build CallGraph

bolt/include/bolt/Core/MCPlusBuilder.h

 //===- bolt/Core/MCPlusBuilder.h - Interface for MCPlus ---------*- 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
 //
 //===----------------------------------------------------------------------===//
 //
public:
 
   virtual MCPhysReg getX86R11() const { llvm_unreachable("not implemented"); }
 
   virtual unsigned getShortBranchOpcode(unsigned Opcode) const {
     llvm_unreachable("not implemented");
     return 0;
   }
 
+  virtual bool replaceZeroIdiom(MCInst &Inst) const {
+    llvm_unreachable("not implemented");
+    return false;
+  }
+
   /// Create increment contents of target by 1 for Instrumentation
   virtual InstructionListType createInstrIncMemory(const MCSymbol *Target,
                                                    MCContext *Ctx,
                                                    bool IsLeaf) const {
     llvm_unreachable("not implemented");
     return InstructionListType();
   }
 

bolt/include/bolt/Passes/ZeroIdiom.h

+//===- bolt/Passes/ZeroIdiom.h ----------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Pass to convert eligible instructions into zero idiom (xor reg, reg).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef BOLT_PASSES_ZEROIDIOM_H
+#define BOLT_PASSES_ZEROIDIOM_H
+
+#include "bolt/Passes/BinaryPasses.h"
+
+namespace llvm {
+namespace bolt {
+
+class DataflowInfoManager;
+
+/// Pass for converting eligible instructions into zero idiom.
+class ZeroIdiomPass : public BinaryFunctionPass {
+  void runOnFunction(BinaryFunction &Function, DataflowInfoManager &Info);
+
+public:
+  explicit ZeroIdiomPass(const cl::opt<bool> &PrintPass)
+      : BinaryFunctionPass(PrintPass) {}
+
+  const char *getName() const override { return "zero-idiom"; }
+
+  void runOnFunctions(BinaryContext &BC) override;
+};
+
+} // end namespace bolt
+} // end namespace llvm
+
+#endif

bolt/lib/Passes/CMakeLists.txt

add_llvm_library(LLVMBOLTPasses
   StackReachingUses.cpp
   StokeInfo.cpp
   TailDuplication.cpp
   ThreeWayBranch.cpp
   ValidateInternalCalls.cpp
   ValidateMemRefs.cpp
   VeneerElimination.cpp
   RetpolineInsertion.cpp
+  ZeroIdiom.cpp
 
   DISABLE_LLVM_LINK_LLVM_DYLIB
 
   LINK_LIBS
   ${LLVM_PTHREAD_LIB}
 
   LINK_COMPONENTS
   AsmPrinter

bolt/lib/Passes/ZeroIdiom.cpp

+//===- bolt/Passes/ZeroIdiom.cpp ------------------------------------------===//
+//
+// 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 implements the Zero Idiom conversion pass.
+//
+//===----------------------------------------------------------------------===//
+
+#include "bolt/Passes/ZeroIdiom.h"
+#include "bolt/Core/ParallelUtilities.h"
+#include "bolt/Passes/BinaryFunctionCallGraph.h"
+#include "bolt/Passes/DataflowInfoManager.h"
+
+#define DEBUG_TYPE "zeroidiom"
+
+namespace llvm {
+namespace bolt {
+
+void ZeroIdiomPass::runOnFunction(BinaryFunction &BF,
+                                  DataflowInfoManager &Info) {
+  BinaryContext &BC = BF.getBinaryContext();
+  LivenessAnalysis &LA = Info.getLivenessAnalysis();
+
+  for (BinaryBasicBlock &BB : BF) {
+    for (MCInst &Inst : BB) {
+      if (LA.isAlive(ProgramPoint(&Inst), BC.MIB->getFlagsReg()))
+        continue;
+      BC.MIB->replaceZeroIdiom(Inst);
+    }
+  }
+}
+
+void ZeroIdiomPass::runOnFunctions(BinaryContext &BC) {
+  if (!BC.isX86())
+    return;
+
+  std::unique_ptr<BinaryFunctionCallGraph> CG(
+      new BinaryFunctionCallGraph(buildCallGraph(BC)));
+  std::unique_ptr<RegAnalysis> RA(
+      new RegAnalysis(BC, &BC.getBinaryFunctions(), &*CG));
+
+  ParallelUtilities::WorkFuncWithAllocTy WorkFun =
+      [&](BinaryFunction &BF, MCPlusBuilder::AllocatorIdTy AllocId) {
+        DataflowInfoManager Info(BF, RA.get(), nullptr, AllocId);
+        runOnFunction(BF, Info);
+      };
+
+  ParallelUtilities::runOnEachFunctionWithUniqueAllocId(
+      BC, ParallelUtilities::SchedulingPolicy::SP_INST_LINEAR, WorkFun, nullptr,
+      "ZeroIdiom");
+}
+
+} // end namespace bolt
+} // end namespace llvm

bolt/lib/Rewrite/BinaryPassManager.cpp

 //===- bolt/Rewrite/BinaryPassManager.cpp - Binary-level pass manager -----===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 

 #include "bolt/Passes/RetpolineInsertion.h"
 #include "bolt/Passes/SplitFunctions.h"
 #include "bolt/Passes/StokeInfo.h"
 #include "bolt/Passes/TailDuplication.h"
 #include "bolt/Passes/ThreeWayBranch.h"
 #include "bolt/Passes/ValidateInternalCalls.h"
 #include "bolt/Passes/ValidateMemRefs.h"
 #include "bolt/Passes/VeneerElimination.h"
+#include "bolt/Passes/ZeroIdiom.h"
 #include "bolt/Utils/CommandLineOpts.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/raw_ostream.h"
 #include <memory>
 #include <numeric>
 
 using namespace llvm;
static cl::opt<bool> PrintVeneerElimination(
     cl::desc("print functions after veneer elimination pass"),
     cl::cat(BoltOptCategory));
 
 static cl::opt<bool>
     PrintUCE("print-uce",
              cl::desc("print functions after unreachable code elimination"),
              cl::Hidden, cl::cat(BoltOptCategory));
 
+static cl::opt<bool>
+    PrintZeroIdiom("print-zero-idiom",
+                   cl::desc("print functions after zero idiom"),
+                   cl::cat(BoltOptCategory));
+
 static cl::opt<bool> RegReAssign(
     "reg-reassign",
     cl::desc(
         "reassign registers so as to avoid using REX prefixes in hot code"),
     cl::cat(BoltOptCategory));
 
 static cl::opt<bool> SimplifyConditionalTailCalls(
     "simplify-conditional-tail-calls",
void BinaryFunctionPassManager::runAllPasses(BinaryContext &BC) {
 
   Manager.registerPass(std::make_unique<LoopInversionPass>());
 
   Manager.registerPass(std::make_unique<TailDuplication>());
 
   Manager.registerPass(std::make_unique<CMOVConversion>(),
                        opts::CMOVConversionFlag);
 
+  Manager.registerPass(std::make_unique<ZeroIdiomPass>(PrintZeroIdiom));
+
   // This pass syncs local branches with CFG. If any of the following
   // passes breaks the sync - they either need to re-run the pass or
   // fix branches consistency internally.
   Manager.registerPass(std::make_unique<FixupBranches>(PrintAfterBranchFixup));
 
   // This pass should come close to last since it uses the estimated hot
   // size of a function to determine the order.  It should definitely
   // also happen after any changes to the call graph are made, e.g. inlining.

bolt/lib/Target/X86/X86MCPlusBuilder.cpp

 //===- bolt/Target/X86/X86MCPlusBuilder.cpp -------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
case X86::JMP_4:
       return X86::JMP_1;
     case X86::JCC_2:
       return X86::JCC_1;
     case X86::JCC_4:
       return X86::JCC_1;
     }
   }
 
+  bool replaceZeroIdiom(MCInst &Inst) const override {
+    unsigned Opcode = Inst.getOpcode();
+
+    // Replace `movl $0x0, %eax` with `xorl %eax, %eax`
+    switch (Opcode) {
+    case X86::MOV64ri:
+    case X86::MOV64ri32:
+    case X86::MOV32ri:
+      auto OpNum = MCPlus::getNumPrimeOperands(Inst) - 1;
+      if (Inst.getOperand(OpNum).isImm() && !Inst.getOperand(OpNum).getImm()) {
+        if (Opcode == X86::MOV32ri)
+          Opcode = X86::XOR32rr;
+        else
+          Opcode = X86::XOR64rr;
+        MCOperand Op = Inst.getOperand(0);
+        Inst.setOpcode(Opcode);
+        Inst.clear();
+        Inst.addOperand(Op);
+        Inst.addOperand(Op);
+        Inst.addOperand(Op);
+      }
+      return true;
+    }
+    return false;
+  }
+
   MCPhysReg getIntArgRegister(unsigned ArgNo) const override {
     // FIXME: this should depend on the calling convention.
     switch (ArgNo) {
     case 0:   return X86::RDI;
     case 1:   return X86::RSI;
     case 2:   return X86::RDX;
     case 3:   return X86::RCX;
     case 4:   return X86::R8;

bolt/test/X86/zero-idiom.s

+# RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown %s -o %t.o
+# RUN: %clang %cflags %t.o -o %t.exe -Wl,-q -nostdlib
+# RUN: llvm-bolt %t.exe -o %t -funcs=_start
+# RUN: llvm-objdump -d --disassemble-symbols=_start %t | FileCheck %s
+# CHECK-NOT: xorl    %edx, %edx
+  .globl _start
+  .type _start, %function
+_start:
+  .cfi_startproc
+  cmpb  $0x0, 0x8(%rax)
+  movl  $0x0, %edx
+  movq  -0x218(%rbp), %r13
+  movq  (%rdi), %rax
+  cmovel  %edx, %ebx
+  .cfi_endproc
+.size _start, .-_start