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.
   assert(InsertionPoint != Insts.begin());
   --InsertionPoint;
+  // 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
+  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;
   // Confirm that InsertionPoint is a terminator instruction.  Calling
   // getTerminatorEdges() on a non-terminator instruction will cause
   // an llvm_unreachable().

[jvoung (off chromium), 2014/09/10 17:17:43]

Maybe this confirmation should be earlier than the comment about
SafeInsertionPoint (seems to be a continuation of // Every block must end in a
terminator instruction.)

[Jim Stichnoth, 2014/09/10 18:29:16]

Actually, the "Every block must..." comment was meant to say that every block
must have at least one instruction and therefore it's valid to decrement
InsertionPoint.

But you're right and it seems better to do the validation before the long-winded
comment.

   (void)(*InsertionPoint)->getTerminatorEdges();
   // 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