1dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//=- AArch64PromoteConstant.cpp --- Promote constant to global for AArch64 -==// 236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// The LLVM Compiler Infrastructure 436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// This file is distributed under the University of Illinois Open Source 636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// License. See LICENSE.TXT for details. 736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 10dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// This file implements the AArch64PromoteConstant pass which promotes constants 11dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// to global variables when this is likely to be more efficient. Currently only 12dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// types related to constant vector (i.e., constant vector, array of constant 13dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// vectors, constant structure with a constant vector field, etc.) are promoted 14dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// to global variables. Constant vectors are likely to be lowered in target 15dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// constant pool during instruction selection already; therefore, the access 16dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// will remain the same (memory load), but the structure types are not split 17dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// into different constant pool accesses for each field. A bonus side effect is 18dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// that created globals may be merged by the global merge pass. 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// FIXME: This pass may be useful for other targets too. 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 23dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "AArch64.h" 2436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/DenseMap.h" 25ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/ADT/SmallPtrSet.h" 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/SmallVector.h" 2737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/ADT/Statistic.h" 2836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Constants.h" 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Function.h" 3136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/GlobalVariable.h" 3237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/IR/IRBuilder.h" 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/InlineAsm.h" 34ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/IR/InstIterator.h" 3536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Instructions.h" 3636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/IntrinsicInst.h" 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Module.h" 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Pass.h" 3936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/CommandLine.h" 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/Debug.h" 414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Support/raw_ostream.h" 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesusing namespace llvm; 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 45dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "aarch64-promote-const" 46dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 4736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Stress testing mode - disable heuristics. 48dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic cl::opt<bool> Stress("aarch64-stress-promote-const", cl::Hidden, 4936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::desc("Promote all vector constants")); 5036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 5136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesSTATISTIC(NumPromoted, "Number of promoted constants"); 5236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesSTATISTIC(NumPromotedUses, "Number of promoted constants uses"); 5336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 55dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// AArch64PromoteConstant 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 5736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace { 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Promotes interesting constant into global variables. 6036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// The motivating example is: 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// static const uint16_t TableA[32] = { 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 41944, 40330, 38837, 37450, 36158, 34953, 33826, 32768, 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 31776, 30841, 29960, 29128, 28340, 27595, 26887, 26215, 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 25576, 24967, 24386, 23832, 23302, 22796, 22311, 21846, 6536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 21400, 20972, 20561, 20165, 19785, 19419, 19066, 18725, 6636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// }; 6736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 6836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// uint8x16x4_t LoadStatic(void) { 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// uint8x16x4_t ret; 7036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// ret.val[0] = vld1q_u16(TableA + 0); 7136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// ret.val[1] = vld1q_u16(TableA + 8); 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// ret.val[2] = vld1q_u16(TableA + 16); 7336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// ret.val[3] = vld1q_u16(TableA + 24); 7436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// return ret; 7536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// } 7636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 77dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// The constants in this example are folded into the uses. Thus, 4 different 7836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// constants are created. 79dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// As their type is vector the cheapest way to create them is to load them 8136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// for the memory. 82dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 83dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Therefore the final assembly final has 4 different loads. With this pass 84dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// enabled, only one load is issued for the constants. 85dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesclass AArch64PromoteConstant : public ModulePass { 8636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 8736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinespublic: 88de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar struct PromotedConstant { 89de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool ShouldConvert = false; 90de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar GlobalVariable *GV = nullptr; 91de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar }; 92de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typedef SmallDenseMap<Constant *, PromotedConstant, 16> PromotionCacheTy; 93de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 94de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar struct UpdateRecord { 95de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Constant *C; 96de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *User; 97de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Op; 98de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 99de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar UpdateRecord(Constant *C, Instruction *User, unsigned Op) 100de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : C(C), User(User), Op(Op) {} 101de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar }; 102de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static char ID; 104dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AArch64PromoteConstant() : ModulePass(ID) {} 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 106dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const char *getPassName() const override { return "AArch64 Promote Constant"; } 10736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Iterate over the functions and promote the interesting constants into 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// global variables with module scope. 110dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool runOnModule(Module &M) override { 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << getPassName() << '\n'); 112de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (skipModule(M)) 113de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Changed = false; 115de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PromotionCacheTy PromotionCache; 116dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto &MF : M) { 117de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Changed |= runOnFunction(MF, PromotionCache); 11836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 11936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Changed; 12036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 12136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 12236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesprivate: 12336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Look for interesting constants used within the given function. 12436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Promote them into global variables, load these global variables within 12536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// the related function, so that the number of inserted load is minimal. 126de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool runOnFunction(Function &F, PromotionCacheTy &PromotionCache); 12736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 12836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // This transformation requires dominator info 129dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 13036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.setPreservesCFG(); 13136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<DominatorTreeWrapperPass>(); 13236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addPreserved<DominatorTreeWrapperPass>(); 13336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 13436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 135ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Type to store a list of Uses. 136de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typedef SmallVector<std::pair<Instruction *, unsigned>, 4> Uses; 13736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Map an insertion point to all the uses it dominates. 138ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typedef DenseMap<Instruction *, Uses> InsertionPoints; 13936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 14036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Find the closest point that dominates the given Use. 141de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *findInsertionPoint(Instruction &User, unsigned OpNo); 14236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 14336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Check if the given insertion point is dominated by an existing 14436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// insertion point. 14536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// If true, the given use is added to the list of dominated uses for 14636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// the related existing point. 14736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \param NewPt the insertion point to be checked 148de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \param User the user of the constant 149de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \param OpNo the operand number of the use 15036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \param InsertPts existing insertion points 15136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \pre NewPt and all instruction in InsertPts belong to the same function 15236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \return true if one of the insertion point in InsertPts dominates NewPt, 15336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// false otherwise 154de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool isDominated(Instruction *NewPt, Instruction *User, unsigned OpNo, 155de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InsertionPoints &InsertPts); 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 15736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Check if the given insertion point can be merged with an existing 15836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// insertion point in a common dominator. 15936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// If true, the given use is added to the list of the created insertion 16036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// point. 16136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \param NewPt the insertion point to be checked 162de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \param User the user of the constant 163de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \param OpNo the operand number of the use 16436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \param InsertPts existing insertion points 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \pre NewPt and all instruction in InsertPts belong to the same function 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \pre isDominated returns false for the exact same parameters. 16736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \return true if it exists an insertion point in InsertPts that could 16836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// have been merged with NewPt in a common dominator, 16936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// false otherwise 170de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool tryAndMerge(Instruction *NewPt, Instruction *User, unsigned OpNo, 171de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InsertionPoints &InsertPts); 17236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Compute the minimal insertion points to dominates all the interesting 17436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// uses of value. 17536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Insertion points are group per function and each insertion point 17636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// contains a list of all the uses it dominates within the related function 177de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \param User the user of the constant 178de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \param OpNo the operand number of the constant 179de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// \param[out] InsertPts output storage of the analysis 180de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void computeInsertionPoint(Instruction *User, unsigned OpNo, 181de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InsertionPoints &InsertPts); 18236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Insert a definition of a new global variable at each point contained in 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// InsPtsPerFunc and update the related uses (also contained in 18536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// InsPtsPerFunc). 186de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void insertDefinitions(Function &F, GlobalVariable &GV, 187de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InsertionPoints &InsertPts); 188de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 189de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// Do the constant promotion indicated by the Updates records, keeping track 190de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar /// of globals in PromotionCache. 191de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar void promoteConstants(Function &F, SmallVectorImpl<UpdateRecord> &Updates, 192de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PromotionCacheTy &PromotionCache); 19336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// Transfer the list of dominated uses of IPI to NewPt in InsertPts. 195ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Append Use to this list and delete the entry of IPI in InsertPts. 196de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar static void appendAndTransferDominatedUses(Instruction *NewPt, 197de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *User, unsigned OpNo, 19836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines InsertionPoints::iterator &IPI, 19936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines InsertionPoints &InsertPts) { 200dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Record the dominated use. 201de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar IPI->second.emplace_back(User, OpNo); 20236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Transfer the dominated uses of IPI to NewPt 20336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Inserting into the DenseMap may invalidate existing iterator. 2044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // Keep a copy of the key to find the iterator to erase. Keep a copy of the 2054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // value so that we don't have to dereference IPI->second. 20636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *OldInstr = IPI->first; 2074c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Uses OldUses = std::move(IPI->second); 2084c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InsertPts[NewPt] = std::move(OldUses); 209dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Erase IPI. 210ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines InsertPts.erase(OldInstr); 21136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 21236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 21336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} // end anonymous namespace 21436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 215dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hineschar AArch64PromoteConstant::ID = 0; 21636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 21736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace llvm { 218dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid initializeAArch64PromoteConstantPass(PassRegistry &); 21936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 22036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 221dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesINITIALIZE_PASS_BEGIN(AArch64PromoteConstant, "aarch64-promote-const", 222dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "AArch64 Promote Constant Pass", false, false) 22336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 224dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesINITIALIZE_PASS_END(AArch64PromoteConstant, "aarch64-promote-const", 225dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "AArch64 Promote Constant Pass", false, false) 22636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 227dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesModulePass *llvm::createAArch64PromoteConstantPass() { 228dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return new AArch64PromoteConstant(); 22936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 23036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 23136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Check if the given type uses a vector type. 23236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool isConstantUsingVectorTy(const Type *CstTy) { 23336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (CstTy->isVectorTy()) 23436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 23536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (CstTy->isStructTy()) { 23636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned EltIdx = 0, EndEltIdx = CstTy->getStructNumElements(); 23736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines EltIdx < EndEltIdx; ++EltIdx) 23836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isConstantUsingVectorTy(CstTy->getStructElementType(EltIdx))) 23936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 24036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else if (CstTy->isArrayTy()) 24136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return isConstantUsingVectorTy(CstTy->getArrayElementType()); 24236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 24336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 24436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 24536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Check if the given use (Instruction + OpIdx) of Cst should be converted into 24636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// a load of a global variable initialized with Cst. 24736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// A use should be converted if it is legal to do so. 24836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// For instance, it is not legal to turn the mask operand of a shuffle vector 24936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// into a load of a global variable. 25036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool shouldConvertUse(const Constant *Cst, const Instruction *Instr, 25136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned OpIdx) { 25236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // shufflevector instruction expects a const for the mask argument, i.e., the 25336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // third argument. Do not promote this use in that case. 25436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<const ShuffleVectorInst>(Instr) && OpIdx == 2) 25536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 25636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 257dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // extractvalue instruction expects a const idx. 25836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<const ExtractValueInst>(Instr) && OpIdx > 0) 25936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 26036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 261dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // extractvalue instruction expects a const idx. 26236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<const InsertValueInst>(Instr) && OpIdx > 1) 26336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 26436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 26536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<const AllocaInst>(Instr) && OpIdx > 0) 26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 26736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 268dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Alignment argument must be constant. 26936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<const LoadInst>(Instr) && OpIdx > 0) 27036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 27136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 272dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Alignment argument must be constant. 27336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<const StoreInst>(Instr) && OpIdx > 1) 27436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 27536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 276dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Index must be constant. 27736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<const GetElementPtrInst>(Instr) && OpIdx > 0) 27836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 27936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 28036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Personality function and filters must be constant. 28136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Give up on that instruction. 28236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<const LandingPadInst>(Instr)) 28336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 28436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 285dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Switch instruction expects constants to compare to. 28636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<const SwitchInst>(Instr)) 28736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 28836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 289dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Expected address must be a constant. 29036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<const IndirectBrInst>(Instr)) 29136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 29236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 293dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Do not mess with intrinsics. 29436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<const IntrinsicInst>(Instr)) 29536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 29636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 297dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Do not mess with inline asm. 29836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const CallInst *CI = dyn_cast<const CallInst>(Instr); 299de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return !(CI && isa<const InlineAsm>(CI->getCalledValue())); 30036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 30136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 30236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Check if the given Cst should be converted into 30336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// a load of a global variable initialized with Cst. 30436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// A constant should be converted if it is likely that the materialization of 30536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// the constant will be tricky. Thus, we give up on zero or undef values. 30636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 30736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \todo Currently, accept only vector related types. 30836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Also we give up on all simple vector type to keep the existing 30936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// behavior. Otherwise, we should push here all the check of the lowering of 31036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// BUILD_VECTOR. By giving up, we lose the potential benefit of merging 31136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// constant via global merge and the fact that the same constant is stored 31236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// only once with this method (versus, as many function that uses the constant 31336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// for the regular approach, even for float). 31436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Again, the simplest solution would be to promote every 31536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// constant and rematerialize them when they are actually cheap to create. 316de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool shouldConvertImpl(const Constant *Cst) { 31736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<const UndefValue>(Cst)) 31836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 31936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 32036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // FIXME: In some cases, it may be interesting to promote in memory 32136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // a zero initialized constant. 32236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // E.g., when the type of Cst require more instructions than the 32336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // adrp/add/load sequence or when this sequence can be shared by several 32436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // instances of Cst. 32536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Ideally, we could promote this into a global and rematerialize the constant 32636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // when it was a bad idea. 32736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Cst->isZeroValue()) 32836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 32936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 33036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Stress) 33136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 33236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 33336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // FIXME: see function \todo 33436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Cst->getType()->isVectorTy()) 33536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 33636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return isConstantUsingVectorTy(Cst->getType()); 33736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 33836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 339de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool 340de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarshouldConvert(Constant &C, 341de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AArch64PromoteConstant::PromotionCacheTy &PromotionCache) { 342de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto Converted = PromotionCache.insert( 343de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::make_pair(&C, AArch64PromoteConstant::PromotedConstant())); 344de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Converted.second) 345de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Converted.first->second.ShouldConvert = shouldConvertImpl(&C); 346de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Converted.first->second.ShouldConvert; 347de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 348ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 349de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarInstruction *AArch64PromoteConstant::findInsertionPoint(Instruction &User, 350de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned OpNo) { 35136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If this user is a phi, the insertion point is in the related 352dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // incoming basic block. 353de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (PHINode *PhiInst = dyn_cast<PHINode>(&User)) 354de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return PhiInst->getIncomingBlock(OpNo)->getTerminator(); 355ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 356de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return &User; 35736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 35836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 359de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool AArch64PromoteConstant::isDominated(Instruction *NewPt, Instruction *User, 360de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned OpNo, 361dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines InsertionPoints &InsertPts) { 36236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 36336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>( 36436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines *NewPt->getParent()->getParent()).getDomTree(); 36536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 366dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Traverse all the existing insertion points and check if one is dominating 367dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // NewPt. If it is, remember that. 368dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto &IPI : InsertPts) { 369dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (NewPt == IPI.first || DT.dominates(IPI.first, NewPt) || 370dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // When IPI.first is a terminator instruction, DT may think that 37136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // the result is defined on the edge. 37236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Here we are testing the insertion point, not the definition. 373dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines (IPI.first->getParent() != NewPt->getParent() && 374dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DT.dominates(IPI.first->getParent(), NewPt->getParent()))) { 375dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // No need to insert this point. Just record the dominated use. 37636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Insertion point dominated by:\n"); 377dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(IPI.first->print(dbgs())); 37836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << '\n'); 379de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar IPI.second.emplace_back(User, OpNo); 38036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 38136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 38236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 38336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 38436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 38536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 386de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool AArch64PromoteConstant::tryAndMerge(Instruction *NewPt, Instruction *User, 387de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned OpNo, 388dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines InsertionPoints &InsertPts) { 38936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>( 39036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines *NewPt->getParent()->getParent()).getDomTree(); 39136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *NewBB = NewPt->getParent(); 39236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 39336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Traverse all the existing insertion point and check if one is dominated by 39436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // NewPt and thus useless or can be combined with NewPt into a common 395dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // dominator. 39636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (InsertionPoints::iterator IPI = InsertPts.begin(), 39736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines EndIPI = InsertPts.end(); 39836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IPI != EndIPI; ++IPI) { 39936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *CurBB = IPI->first->getParent(); 40036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (NewBB == CurBB) { 40136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Instructions are in the same block. 40236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // By construction, NewPt is dominating the other. 40336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Indeed, isDominated returned false with the exact same arguments. 40436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Merge insertion point with:\n"); 40536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(IPI->first->print(dbgs())); 40636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "\nat considered insertion point.\n"); 407de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar appendAndTransferDominatedUses(NewPt, User, OpNo, IPI, InsertPts); 40836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 40936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 41036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 41136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Look for a common dominator 41236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *CommonDominator = DT.findNearestCommonDominator(NewBB, CurBB); 413dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If none exists, we cannot merge these two points. 41436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!CommonDominator) 41536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 41636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 41736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (CommonDominator != NewBB) { 418dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // By construction, the CommonDominator cannot be CurBB. 41936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(CommonDominator != CurBB && 42036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "Instruction has not been rejected during isDominated check!"); 42136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Take the last instruction of the CommonDominator as insertion point 42236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewPt = CommonDominator->getTerminator(); 42336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 42436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // else, CommonDominator is the block of NewBB, hence NewBB is the last 425dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // possible insertion point in that block. 42636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << "Merge insertion point with:\n"); 42736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(IPI->first->print(dbgs())); 42836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << '\n'); 42936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(NewPt->print(dbgs())); 43036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << '\n'); 431de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar appendAndTransferDominatedUses(NewPt, User, OpNo, IPI, InsertPts); 43236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 43336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 43436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 43536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 43636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 437de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid AArch64PromoteConstant::computeInsertionPoint( 438de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *User, unsigned OpNo, InsertionPoints &InsertPts) { 439de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "Considered use, opidx " << OpNo << ":\n"); 440de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(User->print(dbgs())); 441de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << '\n'); 44236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 443de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *InsertionPoint = findInsertionPoint(*User, OpNo); 44436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 445de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "Considered insertion point:\n"); 446de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(InsertionPoint->print(dbgs())); 447de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << '\n'); 44836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 449de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (isDominated(InsertionPoint, User, OpNo, InsertPts)) 450de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return; 451de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // This insertion point is useful, check if we can merge some insertion 452de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // point in a common dominator or if NewPt dominates an existing one. 453de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (tryAndMerge(InsertionPoint, User, OpNo, InsertPts)) 454de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return; 45536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 456de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "Keep considered insertion point\n"); 45736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 458de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // It is definitely useful by its own 459de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InsertPts[InsertionPoint].emplace_back(User, OpNo); 46036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 46136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 462de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic void ensurePromotedGV(Function &F, Constant &C, 463de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AArch64PromoteConstant::PromotedConstant &PC) { 464de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(PC.ShouldConvert && 465de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar "Expected that we should convert this to a global"); 466de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (PC.GV) 467de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return; 468de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PC.GV = new GlobalVariable( 469de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar *F.getParent(), C.getType(), true, GlobalValue::InternalLinkage, nullptr, 470de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar "_PromotedConst", nullptr, GlobalVariable::NotThreadLocal); 471de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PC.GV->setInitializer(&C); 472de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "Global replacement: "); 473de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(PC.GV->print(dbgs())); 474de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << '\n'); 475de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++NumPromoted; 476de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 47736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 478de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid AArch64PromoteConstant::insertDefinitions(Function &F, 479de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar GlobalVariable &PromotedGV, 480de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InsertionPoints &InsertPts) { 48136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef NDEBUG 482de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Do more checking for debug purposes. 483de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree(); 48436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#endif 485de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(!InsertPts.empty() && "Empty uses does not need a definition"); 486de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 487de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (const auto &IPI : InsertPts) { 488de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Create the load of the global variable. 489de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar IRBuilder<> Builder(IPI.first); 490de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LoadInst *LoadedCst = Builder.CreateLoad(&PromotedGV); 491de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "**********\n"); 492de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "New def: "); 493de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(LoadedCst->print(dbgs())); 494de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << '\n'); 49536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 496de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Update the dominated uses. 497de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto Use : IPI.second) { 49836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef NDEBUG 499de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(DT.dominates(LoadedCst, 500de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar findInsertionPoint(*Use.first, Use.second)) && 501de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar "Inserted definition does not dominate all its uses!"); 50236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#endif 503de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG({ 504de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "Use to update " << Use.second << ":"; 505de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Use.first->print(dbgs()); 506de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << '\n'; 507de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar }); 508de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Use.first->setOperand(Use.second, LoadedCst); 509de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++NumPromotedUses; 51036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 51136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 51236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 51336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 514de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid AArch64PromoteConstant::promoteConstants( 515de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Function &F, SmallVectorImpl<UpdateRecord> &Updates, 516de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PromotionCacheTy &PromotionCache) { 517de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Promote the constants. 518de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto U = Updates.begin(), E = Updates.end(); U != E;) { 519de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DEBUG(dbgs() << "** Compute insertion points **\n"); 520de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto First = U; 521de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Constant *C = First->C; 522de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar InsertionPoints InsertPts; 523de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar do { 524de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar computeInsertionPoint(U->User, U->Op, InsertPts); 525de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } while (++U != E && U->C == C); 526de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 527de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &Promotion = PromotionCache[C]; 528de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ensurePromotedGV(F, *C, Promotion); 529de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar insertDefinitions(F, *Promotion.GV, InsertPts); 530de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 53136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 53236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 533de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool AArch64PromoteConstant::runOnFunction(Function &F, 534de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PromotionCacheTy &PromotionCache) { 535dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Look for instructions using constant vector. Promote that constant to a 536dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // global variable. Create as few loads of this variable as possible and 537dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // update the uses accordingly. 538de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<UpdateRecord, 64> Updates; 539f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (Instruction &I : instructions(&F)) { 540ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Traverse the operand, looking for constant vectors. Replace them by a 541ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // load of a global variable of constant vector type. 542de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Use &U : I.operands()) { 543de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Constant *Cst = dyn_cast<Constant>(U); 544ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // There is no point in promoting global values as they are already 545ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // global. Do not promote constant expressions either, as they may 546ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // require some code expansion. 547de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Cst || isa<GlobalValue>(Cst) || isa<ConstantExpr>(Cst)) 548de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 549de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 550de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Check if this constant is worth promoting. 551de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!shouldConvert(*Cst, PromotionCache)) 552de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 553de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 554de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Check if this use should be promoted. 555de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned OpNo = &U - I.op_begin(); 556de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!shouldConvertUse(Cst, &I, OpNo)) 557de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 558de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 559de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Updates.emplace_back(Cst, &I, OpNo); 56036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 56136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 562de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 563de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Updates.empty()) 564de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 565de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 566de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar promoteConstants(F, Updates, PromotionCache); 567de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return true; 56836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 569