Refactor: Use positive field names in VectorizeConfig.

[oota-llvm.git] / include / llvm / Transforms / Utils / SSAUpdaterImpl.h

diff --git a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h
index 82537968444b58c95fe5cb03131a575c51334fe6..a9adbd73c152e590894bb730533575864ddee28a 100644 (file)
--- a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h
+++ b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h
@@ -15,8 +15,16 @@
 #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
 #define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
 
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/ValueHandle.h"
+
 namespace llvm {
 
+class CastInst;
+class PHINode;
 template<typename T> class SSAUpdaterTraits;
 
 template<typename UpdaterT>
@@ -69,7 +77,7 @@ public:
   /// where needed.
   ValT GetValue(BlkT *BB) {
     SmallVector<BBInfo*, 100> BlockList;
-    BuildBlockList(BB, &BlockList);
+    BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
 
     // Special case: bail out if BB is unreachable.
     if (BlockList.size() == 0) {
@@ -78,7 +86,7 @@ public:
       return V;
     }
 
-    FindDominators(&BlockList);
+    FindDominators(&BlockList, PseudoEntry);
     FindPHIPlacement(&BlockList);
     FindAvailableVals(&BlockList);
 
@@ -89,7 +97,7 @@ public:
   /// through its predecessors until reaching blocks with known values.
   /// Create BBInfo structures for the blocks and append them to the block
   /// list.
-  void BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
+  BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
     SmallVector<BBInfo*, 10> RootList;
     SmallVector<BBInfo*, 64> WorkList;
 
@@ -106,17 +114,12 @@ public:
       Preds.clear();
       Traits::FindPredecessorBlocks(Info->BB, &Preds);
       Info->NumPreds = Preds.size();
-      Info->Preds = static_cast<BBInfo**>
-        (Allocator.Allocate(Info->NumPreds * sizeof(BBInfo*),
-                            AlignOf<BBInfo*>::Alignment));
-
-      // Treat an unreachable predecessor as a definition with 'undef'.
-      if (Info->NumPreds == 0) {
-        Info->AvailableVal = Traits::GetUndefVal(Info->BB, Updater);
-        Info->DefBB = Info;
-        RootList.push_back(Info);
-        continue;
-      }
+      if (Info->NumPreds == 0)
+        Info->Preds = 0;
+      else
+        Info->Preds = static_cast<BBInfo**>
+          (Allocator.Allocate(Info->NumPreds * sizeof(BBInfo*),
+                              AlignOf<BBInfo*>::Alignment));
 
       for (unsigned p = 0; p != Info->NumPreds; ++p) {
         BlkT *Pred = Preds[p];
@@ -187,6 +190,7 @@ public:
       }
     }
     PseudoEntry->BlkNum = BlkNum;
+    return PseudoEntry;
   }
 
   /// IntersectDominators - This is the dataflow lattice "meet" operation for
@@ -219,7 +223,7 @@ public:
   /// of root nodes for blocks that define the value.  The dominators for this
   /// subset CFG are not the standard dominators but they are adequate for
   /// placing PHIs within the subset CFG.
-  void FindDominators(BlockListTy *BlockList) {
+  void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {
     bool Changed;
     do {
       Changed = false;
@@ -227,19 +231,29 @@ public:
       for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
              E = BlockList->rend(); I != E; ++I) {
         BBInfo *Info = *I;
+        BBInfo *NewIDom = 0;
 
-        // Start with the first predecessor.
-        assert(Info->NumPreds > 0 && "unreachable block");
-        BBInfo *NewIDom = Info->Preds[0];
-
-        // Iterate through the block's other predecessors.
-        for (unsigned p = 1; p != Info->NumPreds; ++p) {
+        // Iterate through the block's predecessors.
+        for (unsigned p = 0; p != Info->NumPreds; ++p) {
           BBInfo *Pred = Info->Preds[p];
-          NewIDom = IntersectDominators(NewIDom, Pred);
+
+          // Treat an unreachable predecessor as a definition with 'undef'.
+          if (Pred->BlkNum == 0) {
+            Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);
+            (*AvailableVals)[Pred->BB] = Pred->AvailableVal;
+            Pred->DefBB = Pred;
+            Pred->BlkNum = PseudoEntry->BlkNum;
+            PseudoEntry->BlkNum++;
+          }
+
+          if (!NewIDom)
+            NewIDom = Pred;
+          else
+            NewIDom = IntersectDominators(NewIDom, Pred);
         }
 
         // Check if the IDom value has changed.
-        if (NewIDom != Info->IDom) {
+        if (NewIDom && NewIDom != Info->IDom) {
           Info->IDom = NewIDom;
           Changed = true;
         }
@@ -366,7 +380,7 @@ public:
       if (!SomePHI)
         break;
       if (CheckIfPHIMatches(SomePHI)) {
-        RecordMatchingPHI(SomePHI);
+        RecordMatchingPHIs(BlockList);
         break;
       }
       // Match failed: clear all the PHITag values.
@@ -423,38 +437,17 @@ public:
     return true;
   }
 
-  /// RecordMatchingPHI - For a PHI node that matches, record it and its input
-  /// PHIs in both the BBMap and the AvailableVals mapping.
-  void RecordMatchingPHI(PhiT *PHI) {
-    SmallVector<PhiT*, 20> WorkList;
-    WorkList.push_back(PHI);
-
-    // Record this PHI.
-    BlkT *BB = PHI->getParent();
-    ValT PHIVal = Traits::GetPHIValue(PHI);
-    (*AvailableVals)[BB] = PHIVal;
-    BBMap[BB]->AvailableVal = PHIVal;
-
-    while (!WorkList.empty()) {
-      PHI = WorkList.pop_back_val();
-
-      // Iterate through the PHI's incoming values.
-      for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
-             E = Traits::PHI_end(PHI); I != E; ++I) {
-        ValT IncomingVal = I.getIncomingValue();
-        PhiT *IncomingPHI = Traits::ValueIsPHI(IncomingVal, Updater);
-        if (!IncomingPHI) continue;
-        BB = IncomingPHI->getParent();
-        BBInfo *Info = BBMap[BB];
-        if (!Info || Info->AvailableVal)
-          continue;
-
-        // Record the PHI and add it to the worklist.
-        (*AvailableVals)[BB] = IncomingVal;
-        Info->AvailableVal = IncomingVal;
-        WorkList.push_back(IncomingPHI);
+  /// RecordMatchingPHIs - For each PHI node that matches, record it in both
+  /// the BBMap and the AvailableVals mapping.
+  void RecordMatchingPHIs(BlockListTy *BlockList) {
+    for (typename BlockListTy::iterator I = BlockList->begin(),
+           E = BlockList->end(); I != E; ++I)
+      if (PhiT *PHI = (*I)->PHITag) {
+        BlkT *BB = PHI->getParent();
+        ValT PHIVal = Traits::GetPHIValue(PHI);
+        (*AvailableVals)[BB] = PHIVal;
+        BBMap[BB]->AvailableVal = PHIVal;
       }
-    }
   }
 };