[SubZero] Branch optimization

src/IceInstMIPS32.cpp

 //===- subzero/src/IceInstMips32.cpp - Mips32 instruction implementation --===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file
@@ skipping 182 matching lines @@
 InstMIPS32Br::InstMIPS32Br(Cfg *Func, const CfgNode *TargetTrue,
                            const CfgNode *TargetFalse, Operand *Src0,
                            Operand *Src1, const InstMIPS32Label *Label,
                            CondMIPS32::Cond Cond)
     : InstMIPS32(Func, InstMIPS32::Br, 2, nullptr), TargetTrue(TargetTrue),
       TargetFalse(TargetFalse), Label(Label), Predicate(Cond) {
   addSource(Src0);
   addSource(Src1);
 }
 
+CondMIPS32::Cond InstMIPS32::getOppositeCondition(CondMIPS32::Cond Cond) {
+  return InstMIPS32CondAttributes[Cond].Opposite;
+}
+
+bool InstMIPS32Br::optimizeBranch(const CfgNode *NextNode) {
+  // If there is no next block, then there can be no fallthrough to optimize.
+  if (NextNode == nullptr)
+    return false;
+  // Intra-block conditional branches can't be optimized.
+  if (Label != nullptr)
+    return false;
+  // Unconditional branch to the next node can be removed.
+  if (isUnconditionalBranch() && getTargetFalse() == NextNode) {
+    assert(getTargetTrue() == nullptr);
+    setDeleted();
+    return true;
+  }
+  // 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 (getTargetTrue() == nullptr)
+    return false;
+  // If the fallthrough is to the next node, set fallthrough to nullptr to
+  // indicate.
+  if (getTargetTrue() == NextNode) {
+    TargetTrue = nullptr;
+    return true;
+  }
+  // If TargetFalse is the next node, and TargetTrue is not nullptr
+  // then invert the branch condition, swap the targets, and set new
+  // fallthrough to nullptr.
+  if (getTargetFalse() == NextNode) {
+    assert(Predicate != CondMIPS32::AL);
+    setPredicate(getOppositeCondition(getPredicate()));
+    TargetFalse = getTargetTrue();
+    TargetTrue = nullptr;
+    return true;
+  }
+  return false;
+}
+
 bool InstMIPS32Br::repointEdges(CfgNode *OldNode, CfgNode *NewNode) {
   bool Found = false;
   if (TargetFalse == OldNode) {
     TargetFalse = NewNode;
     Found = true;
   }
   if (TargetTrue == OldNode) {
     TargetTrue = NewNode;
     Found = true;
   }
@@ skipping 199 matching lines @@
       case CondMIPS32::LEZ:
       case CondMIPS32::LTZ:
       case CondMIPS32::GEZ:
       case CondMIPS32::GTZ: {
         getSrc(0)->emit(Func);
         Str << ", ";
         break;
       }
       }
       Str << getTargetFalse()->getAsmName();
+      if (getTargetTrue()) {
+        Str << "\n\t"
+            << "b"
+            << "\t" << getTargetTrue()->getAsmName();
+      }
     }
   }
 }
 
 void InstMIPS32Br::dump(const Cfg *Func) const {
   if (!BuildDefs::dump())
     return;
   Ostream &Str = Func->getContext()->getStrDump();
   Str << "\t"
          "b" << InstMIPS32CondAttributes[Predicate].EmitString << "\t";
 
   if (Label) {
     Str << Label->getLabelName();
   } else {
     if (isUnconditionalBranch()) {
       Str << getTargetFalse()->getAsmName();
     } else {
       dumpSources(Func);
       Str << ", ";
       Str << getTargetFalse()->getAsmName();
+      if (getTargetTrue()) {
+        Str << "\n\t"
+            << "b"
+            << "\t" << getTargetTrue()->getAsmName();
+      }
     }
   }
 }
 
 void InstMIPS32Call::emit(const Cfg *Func) const {
   if (!BuildDefs::dump())
     return;
   Ostream &Str = Func->getContext()->getStrEmit();
   assert(getSrcSize() == 1);
   if (llvm::isa<ConstantInteger32>(getCallTarget())) {
@@ skipping 236 matching lines @@
     getSrc(0)->emit(Func);
     return;
   }
 
   // stack to stack
   llvm::report_fatal_error("mov cant copy stack to stack.");
 }
 
 } // end of namespace MIPS32
 } // end of namespace Ice