Subzero: Fix Phi lowering.

src/IceCfgNode.cpp

 //===- subzero/src/IceCfgNode.cpp - Basic block (node) 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 CfgNode class, including the complexities
@@ skipping 97 matching lines @@
 // assumes this ordering of instructions.
 //
 // Note that this transformation takes the Phi dest variables out of
 // SSA form, as there may be assignments to the dest variable in
 // multiple blocks.
 //
 // TODO: Defer this pass until after register allocation, then split
 // critical edges, add the assignments, and lower them.  This should
 // reduce the amount of shuffling at the end of each block.
 void CfgNode::placePhiStores() {
-  // Find the insertion point.  TODO: After branch/compare fusing is
-  // implemented, try not to insert Phi stores between the compare and
-  // conditional branch instructions, otherwise the branch/compare
-  // pattern matching may fail.  However, the branch/compare sequence
-  // will have to be broken if the compare result is read (by the
-  // assignment) before it is written (by the compare).
+  // Find the insertion point.
   InstList::iterator InsertionPoint = Insts.end();
-  // Every block must end in a terminator instruction.
+  // Every block must end in a terminator instruction, and therefore
+  // must have at least one instruction, so it's valid to decrement
+  // InsertionPoint (but assert just in case).
   assert(InsertionPoint != Insts.begin());
   --InsertionPoint;
   // Confirm that InsertionPoint is a terminator instruction.  Calling
   // getTerminatorEdges() on a non-terminator instruction will cause
   // an llvm_unreachable().
   (void)(*InsertionPoint)->getTerminatorEdges();
+  // SafeInsertionPoint is always immediately before the terminator
+  // instruction.  If the block ends in a compare and conditional
+  // branch, it's better to place the Phi store before the compare so
+  // as not to interfere with compare/branch fusing.  However, if the
+  // compare instruction's dest operand is the same as the new
+  // assignment statement's source operand, this can't be done due to
+  // data dependences, so we need to fall back to the
+  // SafeInsertionPoint.  To illustrate:
+  //   ; <label>:95
+  //   %97 = load i8* %96, align 1
+  //   %98 = icmp ne i8 %97, 0
+  //   br i1 %98, label %99, label %2132
+  //   ; <label>:99
+  //   %100 = phi i8 [ %97, %95 ], [ %110, %108 ]
+  //   %101 = phi i1 [ %98, %95 ], [ %111, %108 ]
+  // would be Phi-lowered as:
+  //   ; <label>:95
+  //   %97 = load i8* %96, align 1
+  //   %100_phi = %97 ; can be at InsertionPoint
+  //   %98 = icmp ne i8 %97, 0
+  //   %101_phi = %98 ; must be at SafeInsertionPoint
+  //   br i1 %98, label %99, label %2132
+  //   ; <label>:99
+  //   %100 = %100_phi
+  //   %101 = %101_phi
+  //
+  // TODO(stichnot): It may be possible to bypass this whole
+  // SafeInsertionPoint mechanism.  If a source basic block ends in a
+  // conditional branch:
+  //   labelSource:
+  //   ...
+  //   br i1 %foo, label %labelTrue, label %labelFalse
+  // and a branch target has a Phi involving the branch operand:
+  //   labelTrue:
+  //   %bar = phi i1 [ %foo, %labelSource ], ...
+  // then we actually know the constant i1 value of the Phi operand:
+  //   labelTrue:
+  //   %bar = phi i1 [ true, %labelSource ], ...
+  // It seems that this optimization should be done by clang or opt,
+  // but we could also do it here.
+  InstList::iterator SafeInsertionPoint = InsertionPoint;
+  // Keep track of the dest variable of a compare instruction, so that
+  // we insert the new instruction at the SafeInsertionPoint if the
+  // compare's dest matches the Phi-lowered assignment's source.
+  Variable *CmpInstDest = NULL;
   // If the current insertion point is at a conditional branch
   // instruction, and the previous instruction is a compare
   // instruction, then we move the insertion point before the compare
   // instruction so as not to interfere with compare/branch fusing.
   if (InstBr *Branch = llvm::dyn_cast<InstBr>(*InsertionPoint)) {
     if (!Branch->isUnconditional()) {
       if (InsertionPoint != Insts.begin()) {
         --InsertionPoint;
-        if (!llvm::isa<InstIcmp>(*InsertionPoint) &&
-            !llvm::isa<InstFcmp>(*InsertionPoint)) {
+        if (llvm::isa<InstIcmp>(*InsertionPoint) ||
+            llvm::isa<InstFcmp>(*InsertionPoint)) {
+          CmpInstDest = (*InsertionPoint)->getDest();
+        } else {
           ++InsertionPoint;
         }
       }
     }
   }
 
   // Consider every out-edge.
   for (NodeList::const_iterator I1 = OutEdges.begin(), E1 = OutEdges.end();
        I1 != E1; ++I1) {
     CfgNode *Target = *I1;
     // Consider every Phi instruction at the out-edge.
     for (PhiList::const_iterator I2 = Target->Phis.begin(),
                                  E2 = Target->Phis.end();
          I2 != E2; ++I2) {
       Operand *Operand = (*I2)->getOperandForTarget(this);
       assert(Operand);
       Variable *Dest = (*I2)->getDest();
       assert(Dest);
       InstAssign *NewInst = InstAssign::create(Func, Dest, Operand);
       // If Src is a variable, set the Src and Dest variables to
       // prefer each other for register allocation.
       if (Variable *Src = llvm::dyn_cast<Variable>(Operand)) {
         bool AllowOverlap = false;
         Dest->setPreferredRegister(Src, AllowOverlap);
         Src->setPreferredRegister(Dest, AllowOverlap);
       }
-      Insts.insert(InsertionPoint, NewInst);
+      if (CmpInstDest == Operand)
+        Insts.insert(SafeInsertionPoint, NewInst);
+      else
+        Insts.insert(InsertionPoint, NewInst);
       NewInst->updateVars(this);
     }
   }
 }
 
 // Deletes the phi instructions after the loads and stores are placed.
 void CfgNode::deletePhis() {
   for (PhiList::iterator I = Phis.begin(), E = Phis.end(); I != E; ++I) {
     (*I)->setDeleted();
   }
@@ skipping 324 matching lines @@
          I != E; ++I) {
       if (I != OutEdges.begin())
         Str << ", ";
       Str << "%" << (*I)->getName();
     }
     Str << "\n";
   }
 }
 
 } // end of namespace Ice