100d7baad90040cd117d717ff93c41a22f767759bMatt Arsenault//===- InstCombineWorklist.h - Worklist for InstCombine pass ----*- C++ -*-===// 23df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner// 33df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner// The LLVM Compiler Infrastructure 43df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner// 53df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner// This file is distributed under the University of Illinois Open Source 63df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner// License. See LICENSE.TXT for details. 73df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner// 83df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner//===----------------------------------------------------------------------===// 93df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner 103df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner#ifndef INSTCOMBINE_WORKLIST_H 113df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner#define INSTCOMBINE_WORKLIST_H 123df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner 13a1514e24cc24b050f53a12650e047799358833a1Chandler Carruth#include "llvm/ADT/DenseMap.h" 14a1514e24cc24b050f53a12650e047799358833a1Chandler Carruth#include "llvm/ADT/SmallVector.h" 150b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instruction.h" 163df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner#include "llvm/Support/Compiler.h" 17a1514e24cc24b050f53a12650e047799358833a1Chandler Carruth#include "llvm/Support/Debug.h" 183df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner#include "llvm/Support/raw_ostream.h" 193df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner 20dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "instcombine" 21dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 223df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattnernamespace llvm { 23e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 243df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner/// InstCombineWorklist - This is the worklist management logic for 253df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner/// InstCombine. 2616d8f8bd919b72866e687d99f3aa94a140137c59Duncan Sandsclass LLVM_LIBRARY_VISIBILITY InstCombineWorklist { 273df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner SmallVector<Instruction*, 256> Worklist; 283df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner DenseMap<Instruction*, unsigned> WorklistMap; 29e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 3086a1c32e67b23c5e9e42dff9eb86e99ba15bb42fCraig Topper void operator=(const InstCombineWorklist&RHS) LLVM_DELETED_FUNCTION; 3186a1c32e67b23c5e9e42dff9eb86e99ba15bb42fCraig Topper InstCombineWorklist(const InstCombineWorklist&) LLVM_DELETED_FUNCTION; 323df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattnerpublic: 333df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner InstCombineWorklist() {} 34e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 353df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner bool isEmpty() const { return Worklist.empty(); } 36e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 373df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner /// Add - Add the specified instruction to the worklist if it isn't already 383df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner /// in it. 393df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner void Add(Instruction *I) { 403df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) { 41596aa123f46158639c836f1d53b89a9d7898c4b7Matt Arsenault DEBUG(dbgs() << "IC: ADD: " << *I << '\n'); 423df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner Worklist.push_back(I); 433df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner } 443df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner } 45e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 463df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner void AddValue(Value *V) { 473df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 483df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner Add(I); 493df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner } 50e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 513df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner /// AddInitialGroup - Add the specified batch of stuff in reverse order. 523df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner /// which should only be done when the worklist is empty and when the group 533df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner /// has no duplicates. 543df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner void AddInitialGroup(Instruction *const *List, unsigned NumEntries) { 553df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner assert(Worklist.empty() && "Worklist must be empty to add initial group"); 563df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner Worklist.reserve(NumEntries+16); 57103391d639a19623ed957f366dbd8113f2127c5dBenjamin Kramer WorklistMap.resize(NumEntries); 58596aa123f46158639c836f1d53b89a9d7898c4b7Matt Arsenault DEBUG(dbgs() << "IC: ADDING: " << NumEntries << " instrs to worklist\n"); 59847d3812adab7385c64783c004f679708f0d7924Bill Wendling for (unsigned Idx = 0; NumEntries; --NumEntries) { 603df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner Instruction *I = List[NumEntries-1]; 61847d3812adab7385c64783c004f679708f0d7924Bill Wendling WorklistMap.insert(std::make_pair(I, Idx++)); 623df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner Worklist.push_back(I); 633df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner } 643df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner } 65e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 663df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner // Remove - remove I from the worklist if it exists. 673df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner void Remove(Instruction *I) { 683df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner DenseMap<Instruction*, unsigned>::iterator It = WorklistMap.find(I); 693df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner if (It == WorklistMap.end()) return; // Not in worklist. 70e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 713df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner // Don't bother moving everything down, just null out the slot. 72dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Worklist[It->second] = nullptr; 73e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 743df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner WorklistMap.erase(It); 753df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner } 76e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 773df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner Instruction *RemoveOne() { 78c2d722efbfd4860dcb7a344be2031ec24cb6691fJakub Staszak Instruction *I = Worklist.pop_back_val(); 793df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner WorklistMap.erase(I); 803df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner return I; 813df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner } 82e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 833df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner /// AddUsersToWorkList - When an instruction is simplified, add all users of 843df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner /// the instruction to the work lists because they might get more simplified 853df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner /// now. 863df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner /// 873df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner void AddUsersToWorkList(Instruction &I) { 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (User *U : I.users()) 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Add(cast<Instruction>(U)); 903df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner } 91e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 92e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 933df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner /// Zap - check that the worklist is empty and nuke the backing store for 943df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner /// the map if it is large. 953df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner void Zap() { 963df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner assert(WorklistMap.empty() && "Worklist empty, but map not?"); 97e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 983df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner // Do an explicit clear, this shrinks the map if needed. 993df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner WorklistMap.clear(); 1003df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner } 1013df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner}; 102e673b54bdde4b538cbd67eadac80a15d238c926fJakub Staszak 1033df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner} // end namespace llvm. 1043df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner 105dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#undef DEBUG_TYPE 106dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 1073df5c6fff17296620a79ce80aa8c5939a85f9597Chris Lattner#endif 108