+ Info->NumPreds = Preds->size();
+ Info->Preds = static_cast<MachineSSAUpdater::BBInfo**>
+ (Allocator->Allocate(Info->NumPreds * sizeof(MachineSSAUpdater::BBInfo*),
+ AlignOf<MachineSSAUpdater::BBInfo*>::Alignment));
+}
+
+/// BuildBlockList - Starting from the specified basic block, traverse back
+/// through its predecessors until reaching blocks with known values. Create
+/// BBInfo structures for the blocks and append them to the block list.
+void MachineSSAUpdater::BuildBlockList(MachineBasicBlock *BB,
+ BlockListTy *BlockList,
+ BumpPtrAllocator *Allocator) {
+ AvailableValsTy &AvailableVals = getAvailableVals(AV);
+ BBMapTy *BBMap = getBBMap(BM);
+ SmallVector<BBInfo*, 10> RootList;
+ SmallVector<BBInfo*, 64> WorkList;
+
+ BBInfo *Info = new (*Allocator) BBInfo(BB, 0);
+ (*BBMap)[BB] = Info;
+ WorkList.push_back(Info);
+
+ // Search backward from BB, creating BBInfos along the way and stopping when
+ // reaching blocks that define the value. Record those defining blocks on
+ // the RootList.
+ SmallVector<MachineBasicBlock*, 10> Preds;
+ while (!WorkList.empty()) {
+ Info = WorkList.pop_back_val();
+ Preds.clear();
+ FindPredecessorBlocks(Info, &Preds, Allocator);
+
+ // Treat an unreachable predecessor as a definition with 'undef'.
+ if (Info->NumPreds == 0) {
+ // Insert an implicit_def to represent an undef value.
+ MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
+ Info->BB,
+ Info->BB->getFirstTerminator(),
+ VRC, MRI, TII);
+ Info->AvailableVal = NewDef->getOperand(0).getReg();
+ Info->DefBB = Info;
+ RootList.push_back(Info);
+ continue;
+ }
+
+ for (unsigned p = 0; p != Info->NumPreds; ++p) {
+ MachineBasicBlock *Pred = Preds[p];
+ // Check if BBMap already has a BBInfo for the predecessor block.
+ BBMapTy::value_type &BBMapBucket = BBMap->FindAndConstruct(Pred);
+ if (BBMapBucket.second) {
+ Info->Preds[p] = BBMapBucket.second;
+ continue;
+ }
+
+ // Create a new BBInfo for the predecessor.
+ unsigned PredVal = AvailableVals.lookup(Pred);
+ BBInfo *PredInfo = new (*Allocator) BBInfo(Pred, PredVal);
+ BBMapBucket.second = PredInfo;
+ Info->Preds[p] = PredInfo;
+
+ if (PredInfo->AvailableVal) {
+ RootList.push_back(PredInfo);
+ continue;
+ }
+ WorkList.push_back(PredInfo);
+ }
+ }
+
+ // Now that we know what blocks are backwards-reachable from the starting
+ // block, do a forward depth-first traversal to assign postorder numbers
+ // to those blocks.
+ BBInfo *PseudoEntry = new (*Allocator) BBInfo(0, 0);
+ unsigned BlkNum = 1;
+
+ // Initialize the worklist with the roots from the backward traversal.
+ while (!RootList.empty()) {
+ Info = RootList.pop_back_val();
+ Info->IDom = PseudoEntry;
+ Info->BlkNum = -1;
+ WorkList.push_back(Info);
+ }
+
+ while (!WorkList.empty()) {
+ Info = WorkList.back();
+
+ if (Info->BlkNum == -2) {
+ // All the successors have been handled; assign the postorder number.
+ Info->BlkNum = BlkNum++;
+ // If not a root, put it on the BlockList.
+ if (!Info->AvailableVal)
+ BlockList->push_back(Info);
+ WorkList.pop_back();
+ continue;
+ }
+
+ // Leave this entry on the worklist, but set its BlkNum to mark that its
+ // successors have been put on the worklist. When it returns to the top
+ // the list, after handling its successors, it will be assigned a number.
+ Info->BlkNum = -2;
+
+ // Add unvisited successors to the work list.
+ for (MachineBasicBlock::succ_iterator SI = Info->BB->succ_begin(),
+ E = Info->BB->succ_end(); SI != E; ++SI) {
+ BBInfo *SuccInfo = (*BBMap)[*SI];
+ if (!SuccInfo || SuccInfo->BlkNum)
+ continue;
+ SuccInfo->BlkNum = -1;
+ WorkList.push_back(SuccInfo);
+ }