SSAUpdater.h revision a0c6057061be055faa542d05b2213f2bd779e160
1//===-- SSAUpdater.h - Unstructured SSA Update Tool -------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file declares the SSAUpdater class. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H 15#define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H 16 17namespace llvm { 18 class Value; 19 class BasicBlock; 20 class Use; 21 class PHINode; 22 template<typename T> 23 class SmallVectorImpl; 24 25/// SSAUpdater - This class updates SSA form for a set of values defined in 26/// multiple blocks. This is used when code duplication or another unstructured 27/// transformation wants to rewrite a set of uses of one value with uses of a 28/// set of values. 29class SSAUpdater { 30public: 31 class BBInfo; 32 33private: 34 /// AvailableVals - This keeps track of which value to use on a per-block 35 /// basis. When we insert PHI nodes, we keep track of them here. 36 //typedef DenseMap<BasicBlock*, Value*> AvailableValsTy; 37 void *AV; 38 39 /// PrototypeValue is an arbitrary representative value, which we derive names 40 /// and a type for PHI nodes. 41 Value *PrototypeValue; 42 43 /// BBMap - The GetValueAtEndOfBlock method maintains this mapping from 44 /// basic blocks to BBInfo structures. 45 /// typedef DenseMap<BasicBlock*, BBInfo*> BBMapTy; 46 void *BM; 47 48 /// Allocator - The GetValueAtEndOfBlock method uses this BumpPtrAllocator to 49 /// hold its internal data. The allocator and its storage is created and 50 /// discarded for each invocation of GetValueAtEndOfBlock. 51 void *BPA; 52 53 /// InsertedPHIs - If this is non-null, the SSAUpdater adds all PHI nodes that 54 /// it creates to the vector. 55 SmallVectorImpl<PHINode*> *InsertedPHIs; 56public: 57 /// SSAUpdater constructor. If InsertedPHIs is specified, it will be filled 58 /// in with all PHI Nodes created by rewriting. 59 explicit SSAUpdater(SmallVectorImpl<PHINode*> *InsertedPHIs = 0); 60 ~SSAUpdater(); 61 62 /// Initialize - Reset this object to get ready for a new set of SSA 63 /// updates. ProtoValue is the value used to name PHI nodes. 64 void Initialize(Value *ProtoValue); 65 66 /// AddAvailableValue - Indicate that a rewritten value is available at the 67 /// end of the specified block with the specified value. 68 void AddAvailableValue(BasicBlock *BB, Value *V); 69 70 /// HasValueForBlock - Return true if the SSAUpdater already has a value for 71 /// the specified block. 72 bool HasValueForBlock(BasicBlock *BB) const; 73 74 /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 75 /// live at the end of the specified block. 76 Value *GetValueAtEndOfBlock(BasicBlock *BB); 77 78 /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 79 /// is live in the middle of the specified block. 80 /// 81 /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one 82 /// important case: if there is a definition of the rewritten value after the 83 /// 'use' in BB. Consider code like this: 84 /// 85 /// X1 = ... 86 /// SomeBB: 87 /// use(X) 88 /// X2 = ... 89 /// br Cond, SomeBB, OutBB 90 /// 91 /// In this case, there are two values (X1 and X2) added to the AvailableVals 92 /// set by the client of the rewriter, and those values are both live out of 93 /// their respective blocks. However, the use of X happens in the *middle* of 94 /// a block. Because of this, we need to insert a new PHI node in SomeBB to 95 /// merge the appropriate values, and this value isn't live out of the block. 96 /// 97 Value *GetValueInMiddleOfBlock(BasicBlock *BB); 98 99 /// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 100 /// which use their value in the corresponding predecessor. Note that this 101 /// will not work if the use is supposed to be rewritten to a value defined in 102 /// the same block as the use, but above it. Any 'AddAvailableValue's added 103 /// for the use's block will be considered to be below it. 104 void RewriteUse(Use &U); 105 106private: 107 Value *GetValueAtEndOfBlockInternal(BasicBlock *BB); 108 void FindPHIPlacement(BasicBlock *BB, BBInfo *Info, bool &Changed, 109 unsigned Counter); 110 void FindAvailableVal(BasicBlock *BB, BBInfo *Info, unsigned Counter); 111 void FindExistingPHI(BasicBlock *BB, BBInfo *Info); 112 bool CheckIfPHIMatches(BasicBlock *BB, BBInfo *Info, Value *Val); 113 void RecordMatchingPHI(BasicBlock *BB, BBInfo *Info, PHINode *PHI); 114 void ClearPHITags(BasicBlock *BB, BBInfo *Info, PHINode *PHI); 115 116 void operator=(const SSAUpdater&); // DO NOT IMPLEMENT 117 SSAUpdater(const SSAUpdater&); // DO NOT IMPLEMENT 118}; 119 120} // End llvm namespace 121 122#endif 123