SSAUpdater.h revision 0bef562ea253878ee92a1eaf6db05b0c2edfa74c
193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner//===-- SSAUpdater.h - Unstructured SSA Update Tool -------------*- C++ -*-===// 293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// The LLVM Compiler Infrastructure 493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// This file is distributed under the University of Illinois Open Source 693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// License. See LICENSE.TXT for details. 793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner//===----------------------------------------------------------------------===// 993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 1093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// This file declares the SSAUpdater class. 1193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 1293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner//===----------------------------------------------------------------------===// 1393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 1493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H 1593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H 1693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 1793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnernamespace llvm { 1893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner class Value; 1993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner class BasicBlock; 2093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner class Use; 21f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner class PHINode; 22f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner template<typename T> 23f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner class SmallVectorImpl; 2493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 2593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// SSAUpdater - This class updates SSA form for a set of values defined in 2693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// multiple blocks. This is used when code duplication or another unstructured 2793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// transformation wants to rewrite a set of uses of one value with uses of a 2893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// set of values. 2993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerclass SSAUpdater { 3093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// AvailableVals - This keeps track of which value to use on a per-block 3193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// basis. When we insert PHI nodes, we keep track of them here. We use 3293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// WeakVH's for the value of the map because we RAUW PHI nodes when we 3393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// eliminate them, and want the WeakVH to track this. 3493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner //typedef DenseMap<BasicBlock*, TrackingVH<Value> > AvailableValsTy; 3593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner void *AV; 3693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 3793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// PrototypeValue is an arbitrary representative value, which we derive names 3893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// and a type for PHI nodes. 3993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner Value *PrototypeValue; 4093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 4193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// IncomingPredInfo - We use this as scratch space when doing our recursive 4293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// walk. This should only be used in GetValueInBlockInternal, normally it 4393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// should be empty. 4493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner //std::vector<std::pair<BasicBlock*, TrackingVH<Value> > > IncomingPredInfo; 4593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner void *IPI; 46f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner 47f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner /// InsertedPHIs - If this is non-null, the SSAUpdater adds all PHI nodes that 48f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner /// it creates to the vector. 49f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner SmallVectorImpl<PHINode*> *InsertedPHIs; 5093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerpublic: 51f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner /// SSAUpdater constructor. If InsertedPHIs is specified, it will be filled 52f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner /// in with all PHI Nodes created by rewriting. 53f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner SSAUpdater(SmallVectorImpl<PHINode*> *InsertedPHIs = 0); 5493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner ~SSAUpdater(); 5593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 5693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// Initialize - Reset this object to get ready for a new set of SSA 5793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// updates. ProtoValue is the value used to name PHI nodes. 5893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner void Initialize(Value *ProtoValue); 5993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 601a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// AddAvailableValue - Indicate that a rewritten value is available at the 611a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// end of the specified block with the specified value. 6293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner void AddAvailableValue(BasicBlock *BB, Value *V); 630bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner 640bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner /// HasValueForBlock - Return true if the SSAUpdater already has a value for 650bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner /// the specified block. 660bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner bool HasValueForBlock(BasicBlock *BB) const; 6793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 685fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 695fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner /// live at the end of the specified block. 705fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner Value *GetValueAtEndOfBlock(BasicBlock *BB); 7193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 721a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 731a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// is live in the middle of the specified block. 741a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// 751a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one 761a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// important case: if there is a definition of the rewritten value after the 771a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// 'use' in BB. Consider code like this: 781a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// 791a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// X1 = ... 801a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// SomeBB: 811a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// use(X) 821a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// X2 = ... 831a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// br Cond, SomeBB, OutBB 841a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// 851a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// In this case, there are two values (X1 and X2) added to the AvailableVals 861a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// set by the client of the rewriter, and those values are both live out of 871a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// their respective blocks. However, the use of X happens in the *middle* of 881a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// a block. Because of this, we need to insert a new PHI node in SomeBB to 891a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// merge the appropriate values, and this value isn't live out of the block. 901a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// 911a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Value *GetValueInMiddleOfBlock(BasicBlock *BB); 921a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner 9393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner /// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 941a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// which use their value in the corresponding predecessor. Note that this 951a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// will not work if the use is supposed to be rewritten to a value defined in 961a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// the same block as the use, but above it. Any 'AddAvailableValue's added 971a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// for the use's block will be considered to be below it. 9893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner void RewriteUse(Use &U); 9993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 10093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerprivate: 1015fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner Value *GetValueAtEndOfBlockInternal(BasicBlock *BB); 10293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner void operator=(const SSAUpdater&); // DO NOT IMPLEMENT 10393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner SSAUpdater(const SSAUpdater&); // DO NOT IMPLEMENT 10493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner}; 10593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 10693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} // End llvm namespace 10793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 10893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#endif 109