Subzero: Add branch optimization.

src/IceInstX8632.cpp

 //===- subzero/src/IceInstX8632.cpp - X86-32 instruction implementation ---===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the InstX8632 and OperandX8632 classes,
 // primarily the constructors and the dump()/emit() methods.
 //
 //===----------------------------------------------------------------------===//
 
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 #include "IceInst.h"
 #include "IceInstX8632.h"
 #include "IceTargetLoweringX8632.h"
 #include "IceOperand.h"
 
 namespace Ice {
 
 namespace {
 
 const struct InstX8632BrAttributes_ {
+  InstX8632::BrCond Opposite;
   const char *DisplayString;
   const char *EmitString;
 } InstX8632BrAttributes[] = {
-#define X(tag, dump, emit)                                                     \
-  { dump, emit }                                                               \
+#define X(tag, opp, dump, emit)                                                \
+  { InstX8632::opp, dump, emit }                                               \
   ,
     ICEINSTX8632BR_TABLE
 #undef X
   };
 
 const struct InstX8632CmppsAttributes_ {
   const char *EmitString;
 } InstX8632CmppsAttributes[] = {
 #define X(tag, emit)                                                           \
   { emit }                                                                     \
@@ skipping 79 matching lines @@
 InstX8632Label::InstX8632Label(Cfg *Func, TargetX8632 *Target)
     : InstX8632(Func, InstX8632::Label, 0, NULL),
       Number(Target->makeNextLabelNumber()) {}
 
 IceString InstX8632Label::getName(const Cfg *Func) const {
   char buf[30];
   snprintf(buf, llvm::array_lengthof(buf), "%u", Number);
   return ".L" + Func->getFunctionName() + "$local$__" + buf;
 }
 
-InstX8632Br::InstX8632Br(Cfg *Func, CfgNode *TargetTrue, CfgNode *TargetFalse,
-                         InstX8632Label *Label, InstX8632::BrCond Condition)
+InstX8632Br::InstX8632Br(Cfg *Func, const CfgNode *TargetTrue,
+                         const CfgNode *TargetFalse,
+                         const InstX8632Label *Label,
+                         InstX8632::BrCond Condition)
     : InstX8632(Func, InstX8632::Br, 0, NULL), Condition(Condition),
       TargetTrue(TargetTrue), TargetFalse(TargetFalse), Label(Label) {}
 
+bool InstX8632Br::optimizeBranch(const CfgNode *NextNode) {
+  // If there is no next block, then there can be no fallthrough to
+  // optimize.
+  if (NextNode == NULL)
+    return false;
+  // Intra-block conditional branches can't be optimized.
+  if (Label)
+    return false;
+  // If there is no fallthrough node, such as a non-default case label
+  // for a switch instruction, then there is no opportunity to
+  // optimize.
+  if (getTargetFalse() == NULL)
+    return false;
+
+  // Unconditional branch to the next node can be removed.
+  if (Condition == Br_None && getTargetFalse() == NextNode) {
+    assert(getTargetTrue() == NULL);
+    setDeleted();
+    return true;
+  }
+  // If the fallthrough is to the next node, set fallthrough to NULL
+  // to indicate.
+  if (getTargetFalse() == NextNode) {
+    TargetFalse = NULL;
+    return true;
+  }
+  // If TargetTrue is the next node, and TargetFalse is non-NULL
+  // (which was already tested above), then invert the branch
+  // condition, swap the targets, and set new fallthrough to NULL.
+  if (getTargetTrue() == NextNode) {
+    assert(Condition != Br_None);
+    Condition = InstX8632BrAttributes[Condition].Opposite;
+    TargetTrue = getTargetFalse();
+    TargetFalse = NULL;
+    return true;
+  }
+  return false;
+}
+
 InstX8632Call::InstX8632Call(Cfg *Func, Variable *Dest, Operand *CallTarget)
     : InstX8632(Func, InstX8632::Call, 1, Dest) {
   HasSideEffects = true;
   addSource(CallTarget);
 }
 
 InstX8632Cmov::InstX8632Cmov(Cfg *Func, Variable *Dest, Operand *Source,
                              InstX8632::BrCond Condition)
     : InstX8632(Func, InstX8632::Cmov, 2, Dest), Condition(Condition) {
   // The final result is either the original Dest, or Source, so mark
@@ skipping 1342 matching lines @@
   }
   Str << "(";
   if (Func)
     Var->dump(Func);
   else
     Var->dump(Str);
   Str << ")";
 }
 
 } // end of namespace Ice