summaryrefslogtreecommitdiffstats
path: root/llvm/pass/StateMappingPass.cpp
diff options
context:
space:
mode:
authorTimothy Pearson <tpearson@raptorengineering.com>2019-11-29 19:00:14 -0600
committerTimothy Pearson <tpearson@raptorengineering.com>2019-11-29 19:02:28 -0600
commit4b3250c5073149c59c5c11e06c2c0d93b6a9f5ff (patch)
treedce73321255f834f7b2d4c16fa49760edb534f27 /llvm/pass/StateMappingPass.cpp
parenta58047f7fbb055677e45c9a7d65ba40fbfad4b92 (diff)
downloadhqemu-2.5.1_overlay.zip
hqemu-2.5.1_overlay.tar.gz
Initial overlay of HQEMU 2.5.2 changes onto underlying 2.5.1 QEMU GIT tree2.5.1_overlay
Diffstat (limited to 'llvm/pass/StateMappingPass.cpp')
-rw-r--r--llvm/pass/StateMappingPass.cpp885
1 files changed, 885 insertions, 0 deletions
diff --git a/llvm/pass/StateMappingPass.cpp b/llvm/pass/StateMappingPass.cpp
new file mode 100644
index 0000000..0d9dd9b
--- /dev/null
+++ b/llvm/pass/StateMappingPass.cpp
@@ -0,0 +1,885 @@
+/*
+ * (C) 2010 by Computer System Laboratory, IIS, Academia Sinica, Taiwan.
+ * See COPYRIGHT in top-level directory.
+ */
+
+#include "llvm-debug.h"
+#include "llvm-opc.h"
+#include "llvm-target.h"
+#include "llvm-pass.h"
+
+#define PASS_NAME "StateMapping"
+
+
+/*
+ * StateMappingPass is used to eliminate the redundant loads and stores to the
+ * CPUArchState. The loads and stores of the guest memory operations are not
+ * removed in order not to violate the memory model of the guest architecture.
+ *
+ * The state mapping rules are:
+ * - A guest state is not overlapped: (i.e., same access size)
+ * - Same type: map to this type.
+ * - Different type: select type in the order: vector, float and integer;
+ * use bitcast to convert between different types.
+ * - A guest state is overlapped with other state(s):
+ * - Query StateType to find state size (i.e., boundary) and type:
+ * - Vector type: use insert/extract to manipulate a vector element.
+ * - Other types: use shift to manipulate a vector element.
+ */
+class StateMappingPass : public FunctionPass {
+ IRFactory *IF; /* Uplink to the IRFactory */
+
+public:
+ static char ID;
+ explicit StateMappingPass() : FunctionPass(ID) {}
+ explicit StateMappingPass(IRFactory *IF) : FunctionPass(ID), IF(IF) {}
+
+ bool runOnFunction(Function &F);
+};
+
+struct StateMapping {
+ StateMapping()
+ : State(nullptr), Addr(nullptr), Ty(nullptr), AI(nullptr),
+ hasLoad(false), hasStore(false) {}
+
+ StateData *State;
+ Value *Addr;
+ Type *Ty;
+ AllocaInst *AI;
+ bool hasLoad;
+ bool hasStore;
+
+ intptr_t getSize() { return State->End - State->Start; }
+ intptr_t getStart() { return State->Start; }
+ intptr_t getEnd() { return State->End; }
+ Value *getAddr() { return Addr; }
+ Type *getType() { return Ty; }
+ bool isVector() { return Ty->isVectorTy(); }
+
+ bool overlap(StateRange &Range) {
+ if (Range.empty())
+ return false;
+ intptr_t Start = getStart();
+ intptr_t End = getEnd();
+ auto I = --Range.upper_bound(Start);
+ for (; I != Range.end() && I->first < End; ++I) {
+ if (I->second > Start)
+ return true;
+ }
+ return false;
+ }
+};
+
+struct ElementInfo {
+ ElementInfo() : Shift(0), NumElts(0), EltTy(nullptr), StateTy(nullptr) {}
+
+ intptr_t Shift;
+ unsigned NumElts;
+ Type *EltTy;
+ Type *StateTy;
+};
+
+class StateMapper {
+ typedef std::vector<StateMapping> StateMapList;
+
+ IRFactory *IF;
+ const DataLayout *DL;
+ Instruction *CPU; /* The CPU pointer */
+ Instruction *PreCastPos; /* The position to cast CPU states */
+ Instruction *PreLoadPos; /* The position to preload CPU states */
+ IVec toErase; /* The instructions to be removed */
+
+ FlatType &StateType;
+ StateAnalyzer Analyzer;
+ StateMapList StateMaps;
+
+public:
+ StateMapper(IRFactory *IF)
+ : IF(IF), DL(IF->getDL()), StateType(IF->getTranslator().getStateType()),
+ Analyzer(DL) {}
+
+ bool run(Function &F) {
+ if (!init(F))
+ return false;
+
+ AnalyzeState(F);
+ if (!StateMaps.empty())
+ PromoteState(F);
+
+ ProcessErase(toErase);
+ return true;
+ }
+
+ /* Rearrange instructions in the 'init' block. */
+ bool init(Function &F);
+
+ /* Analyze instructions in a Function that access CPU states. */
+ void AnalyzeState(Function &F);
+
+ /* Compute state mapping information. */
+ void ComputeStateMap(StateMapping &StateMap, StateData &State);
+
+ /* Determine if the state can be operated as a vector. */
+ Type *TryVectorState(StateData &State, Type *Ty);
+
+ /* Map state references to the virtual states. */
+ void PromoteState(Function &F);
+
+ /* Rewrite state loads and stores. */
+ void RewriteLoad(StateMapping &StateMap, StateRef &Ref);
+ void RewriteStore(StateMapping &StateMap, StateRef &Ref);
+ void RewriteLoadVector(StateMapping &StateMap, StateRef &Ref);
+ void RewriteStoreVector(StateMapping &StateMap, StateRef &Ref);
+
+ /* Compute state and element types for element insertion and extraction. */
+ void getElementInfo(StateMapping &StateMap, StateRef &Ref, ElementInfo &Info);
+
+ /* Sync CPU states around helper calls. */
+ void SyncHelperState();
+
+ /* Store dirty states at the leaf blocks. */
+ void ProcessExitBB(BasicBlock *BB);
+
+ /* Get the pointer without GEP and BitCast. */
+ void StripPointer(Value *V, IVec &IV);
+
+ /* Move the pointer before InsertPos. */
+ void MoveStatePointer(Value *V);
+
+ /* Load state from Src and store it to Dest. */
+ void CopyState(Value *Dest, Value *Src, Instruction *InsertPos);
+
+ bool isLegalState(Value *Ptr, intptr_t &Off);
+
+ /* Return true if the input is alias of a state pointer. */
+ bool isStatePointer(Value *V) {
+ if (auto BCI = dyn_cast<BitCastInst>(V)) {
+ if (BCI->getOperand(0) == CPU)
+ return true;
+ return isStatePointer(BCI->getOperand(0));
+ } else if (auto GEP = dyn_cast<GetElementPtrInst>(V))
+ return GEP->getOperand(0) == CPU;
+ return false;
+ }
+
+ bool isSimpleFunction(Function *F) {
+ HelperMap &Helpers = IF->getHelpers();
+ if (Helpers.find(F->getName()) == Helpers.end() ||
+ Helpers[F->getName()]->hasNestedCall)
+ return false;
+ return true;
+ }
+
+ Value *ConvertType(Value *V, Type *Ty, Instruction *InsertPos) {
+ return V->getType() == Ty ? V : new BitCastInst(V, Ty, "", InsertPos);
+ }
+};
+
+/* Return a pre-defined state name. */
+static std::string getStateName(intptr_t Off)
+{
+#if defined(TARGET_I386)
+ if (Off == offsetof(CPUArchState,xmm_regs[0])) return "xmm0";
+ if (Off == offsetof(CPUArchState,xmm_regs[1])) return "xmm1";
+ if (Off == offsetof(CPUArchState,xmm_regs[2])) return "xmm2";
+ if (Off == offsetof(CPUArchState,xmm_regs[3])) return "xmm3";
+ if (Off == offsetof(CPUArchState,xmm_regs[4])) return "xmm4";
+ if (Off == offsetof(CPUArchState,xmm_regs[5])) return "xmm5";
+ if (Off == offsetof(CPUArchState,xmm_regs[6])) return "xmm6";
+ if (Off == offsetof(CPUArchState,xmm_regs[7])) return "xmm7";
+ if (Off == offsetof(CPUArchState,xmm_t0)) return "xmm_t0";
+#endif
+ return "";
+}
+
+/* Determine if the offset is to access the temporary state. */
+static inline bool isLocalState(intptr_t Off)
+{
+#if defined(TARGET_I386)
+ if (Off == offsetof(CPUArchState, xmm_t0))
+ return true;
+#endif
+ return false;
+}
+
+/* Return states that should be ignored during state mapping. */
+static bool isSkipState(intptr_t Off)
+{
+ if (Off == (intptr_t)(offsetof(CPUState, tcg_exit_req) - ENV_OFFSET))
+ return true;
+
+#define stateof(X) \
+ (Off >= (intptr_t)offsetof(CPUArchState,X) && \
+ Off < (intptr_t)(offsetof(CPUArchState,X) + sizeof(((CPUArchState*)0)->X)))
+#define is_fpstatus(X) \
+ (stateof(X.float_detect_tininess) || \
+ stateof(X.float_rounding_mode) || \
+ stateof(X.float_exception_flags) || \
+ stateof(X.floatx80_rounding_precision) || \
+ stateof(X.flush_to_zero) || \
+ stateof(X.flush_inputs_to_zero) || \
+ stateof(X.default_nan_mode))
+
+#if defined(TARGET_ARM)
+ if (is_fpstatus(vfp.fp_status) || is_fpstatus(vfp.standard_fp_status))
+ return true;
+#elif defined(TARGET_I386)
+ if (is_fpstatus(fp_status))
+ return true;
+#endif
+ return false;
+
+#undef stateof
+#undef is_fpstatus
+}
+
+/* Check if the state is legal for state mapping. A legal state must have CPU
+ * as the base pointer, plus a positive constant offset. */
+bool StateMapper::isLegalState(Value *Ptr, intptr_t &Off)
+{
+ Value *Base = getBaseWithConstantOffset(DL, Ptr, Off);
+ if (Off < 0)
+ return false;
+ if (Base == CPU && !isSkipState(Off) && !IRFactory::isStateOfPC(Off))
+ return true;
+ return false;
+}
+
+/* Get the pointer without GEP and BitCast. The stripped GEP and BitCast
+ * instructions are returned to the caller. */
+void StateMapper::StripPointer(Value *V, IVec &IV)
+{
+ std::set<Value *> Visited;
+ Visited.insert(V);
+ do {
+ if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) {
+ IV.push_back(GEP);
+ V = GEP->getOperand(0);
+ } else if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
+ IV.push_back(BCI);
+ V = BCI->getOperand(0);
+ } else
+ return;
+ if (Visited.find(V) != Visited.end())
+ break;
+ Visited.insert(V);
+ } while (true);
+}
+
+/* Move the pointer before InsertPos. */
+void StateMapper::MoveStatePointer(Value *V)
+{
+ IVec toMove;
+ StripPointer(V, toMove);
+ while (!toMove.empty()) {
+ Instruction *I = toMove.back();
+ toMove.pop_back();
+ if (I->getParent() == CPU->getParent())
+ continue;
+ I->moveBefore(PreCastPos);
+ }
+}
+
+/* Copy state data from src address to destination address. */
+void StateMapper::CopyState(Value *Dest, Value *Src, Instruction *InsertPos)
+{
+ if (!isa<AllocaInst>(Src)) {
+ MoveStatePointer(Src);
+ LoadInst *LI = new LoadInst(Src, "", false, InsertPos);
+ new StoreInst(LI, Dest, false, InsertPos);
+
+ if (Src->getType()->getPointerElementType()->isVectorTy())
+ LI->setAlignment(4);
+ } else {
+ MoveStatePointer(Dest);
+ LoadInst *LI = new LoadInst(Src, "", false, InsertPos);
+ StoreInst *SI = new StoreInst(LI, Dest, false, InsertPos);
+
+ if (Dest->getType()->getPointerElementType()->isVectorTy())
+ SI->setAlignment(4);
+ }
+}
+
+/* Store dirty states at the leaf blocks. */
+void StateMapper::ProcessExitBB(BasicBlock *BB)
+{
+ Instruction *InsertPos = nullptr;
+ for (auto BI = BB->begin(), BE = BB->end(); BI != BE; ++BI) {
+ if (MDFactory::isExit(&*BI)) {
+ InsertPos = &*BI;
+ break;
+ }
+ }
+ if (!InsertPos)
+ InsertPos = BB->getTerminator();
+
+ for (auto &StateMap : StateMaps) {
+ if (!StateMap.hasStore || isLocalState(StateMap.getStart()))
+ continue;
+ CopyState(StateMap.Addr, StateMap.AI, InsertPos);
+ }
+}
+
+/* Sync CPU states around helper calls. */
+void StateMapper::SyncHelperState()
+{
+ CallList &Calls = Analyzer.getCalls();
+ if (Calls.empty())
+ return;
+
+ /*
+ * Rules of syncing states around calls:
+ * 1. Dirty states (i.e., stores) are written back before calls.
+ * 2. All states, including loads and stores, are read back after calls.
+ *
+ * If the helper is a simple function, only dependent states are synced.
+ * If the helper is a complicated function, all states are synced.
+ */
+ HelperMap &Helpers = IF->getHelpers();
+ DenseMap<CallInst*, std::set<unsigned> > StoreBeforeCall;
+ DenseMap<CallInst*, std::set<unsigned> > LoadAfterCall;
+
+ for (auto CI : Calls) {
+ Function *Func = CI->getCalledFunction();
+ std::string Name = Func->getName();
+
+ if (isSimpleFunction(Func)) {
+ /* A pre-defined helper without nested call. */
+ HelperInfo *Helper = Helpers[Name];
+ for (unsigned i = 0, e = StateMaps.size(); i != e; ++i) {
+ auto &StateMap = StateMaps[i];
+ if (StateMap.hasStore && StateMap.overlap(Helper->StateUse))
+ StoreBeforeCall[CI].insert(i);
+
+ if (StateMap.overlap(Helper->StateDef))
+ LoadAfterCall[CI].insert(i);
+
+ if (Helper->mayConflictArg) {
+ unsigned NumArgs = CI->getNumArgOperands();
+ for (unsigned j = 1; j < NumArgs; ++j) {
+ intptr_t Off = 0;
+ Value *Arg = CI->getArgOperand(j);
+ if (!isLegalState(Arg, Off))
+ continue;
+ if (Off + Helper->ConflictSize <= StateMap.getStart() ||
+ Off >= StateMap.getEnd())
+ continue;
+ if (StateMap.hasStore)
+ StoreBeforeCall[CI].insert(i);
+ LoadAfterCall[CI].insert(i);
+ }
+ }
+ }
+ } else {
+ /* Sync states for a complicated function (an unknown helper or a
+ * helper with nested calls). */
+ for (unsigned i = 0, e = StateMaps.size(); i != e; ++i) {
+ auto &StateMap = StateMaps[i];
+ if (StateMap.hasStore)
+ StoreBeforeCall[CI].insert(i);
+ LoadAfterCall[CI].insert(i);
+ }
+ }
+ }
+
+ /* Perform state syncing. */
+ for (auto CI : Calls) {
+ Instruction *InsertPos = CI;
+
+ if (!StoreBeforeCall.empty()) {
+ for (auto i : StoreBeforeCall[CI]) {
+ auto &StateMap = StateMaps[i];
+ CopyState(StateMap.Addr, StateMap.AI, InsertPos);
+ }
+ }
+
+ InsertPos = &*std::next(BasicBlock::iterator(InsertPos));
+ if (isa<UnreachableInst>(InsertPos)) {
+ /* No read back is required after tail call. */
+ continue;
+ }
+
+ if (!LoadAfterCall.empty()) {
+ for (auto i : LoadAfterCall[CI]) {
+ auto &StateMap = StateMaps[i];
+ CopyState(StateMap.AI, StateMap.Addr, InsertPos);
+ }
+ }
+ }
+}
+
+static inline bool isSameSize(StateMapping &StateMap, StateRef &Ref)
+{
+ return StateMap.getSize() == Ref.getSize();
+}
+
+/* Compute state and element types for element insertion and extraction. */
+void StateMapper::getElementInfo(StateMapping &StateMap, StateRef &Ref,
+ ElementInfo &Info)
+{
+ intptr_t StateSize = StateMap.getSize();
+ intptr_t Size = Ref.getSize();
+ intptr_t Shift = Ref.Start - StateMap.getStart();
+ Type *StateTy = StateMap.getType();
+ LLVMContext &Context = StateTy->getContext();
+
+ if (!StateMap.isVector()) {
+ /* Use int-N to emulate the state. */
+ Info.NumElts = 1;
+ Info.EltTy = Type::getIntNTy(Context, Size * 8);
+ Info.StateTy = Type::getIntNTy(Context, StateSize * 8);
+ Info.Shift = Shift;
+ return;
+ }
+
+ /* The state is emulated as a vector. */
+ if (StateSize % Size == 0 && Shift % Size == 0) {
+ Type *EltTy = Type::getIntNTy(Context, Size * 8);
+
+ Info.NumElts = 1;
+ Info.EltTy = EltTy;
+ Info.StateTy = VectorType::get(EltTy, StateSize / Size);
+ Info.Shift = Shift / Size;
+ } else {
+ VectorType *VecTy = cast<VectorType>(StateTy);
+ Type *EltTy = VecTy->getScalarType();
+ intptr_t EltSize = DL->getTypeSizeInBits(EltTy) / 8;
+
+ Info.NumElts = Size / EltSize;
+ Info.EltTy = VectorType::get(EltTy, Info.NumElts);
+ Info.StateTy = StateTy;
+ Info.Shift = Shift / EltSize;
+ }
+}
+
+void StateMapper::RewriteLoad(StateMapping &StateMap, StateRef &Ref)
+{
+ LoadInst *LI = cast<LoadInst>(Ref.I);
+ Type *Ty = LI->getType();
+ Instruction *InsertPos = LI;
+
+ /* The same reference size as the state size. */
+ if (isSameSize(StateMap, Ref)) {
+ Value *V = new LoadInst(StateMap.AI, "", false, InsertPos);
+ V = ConvertType(V, Ty, InsertPos);
+ LI->replaceAllUsesWith(V);
+ toErase.push_back(LI);
+ return;
+ }
+
+ if (StateMap.isVector()) {
+ RewriteLoadVector(StateMap, Ref);
+ return;
+ }
+
+ /* This is a non-vector state. Transform the state to the type of Int-N
+ * and use logical shift to extract/insert element data. */
+ ElementInfo Info;
+ getElementInfo(StateMap, Ref, Info);
+
+ Value *V = new LoadInst(StateMap.AI, "", false, InsertPos);
+ V = ConvertType(V, Info.StateTy, InsertPos);
+
+ /* Extract the element. */
+ if (Info.Shift) {
+ Value *Shift = ConstantInt::get(V->getType(), Info.Shift * 8);
+ V = BinaryOperator::Create(Instruction::LShr, V, Shift, "", InsertPos);
+ }
+ V = new TruncInst(V, Info.EltTy, "", InsertPos);
+ V = ConvertType(V, Ty, InsertPos);
+
+ LI->replaceAllUsesWith(V);
+ toErase.push_back(LI);
+}
+
+void StateMapper::RewriteStore(StateMapping &StateMap, StateRef &Ref)
+{
+ StoreInst *SI = cast<StoreInst>(Ref.I);
+ Value *Data = SI->getValueOperand();
+ Instruction *InsertPos = SI;
+
+ /* The same reference size as the state size. */
+ if (isSameSize(StateMap, Ref)) {
+ Value *V = ConvertType(Data, StateMap.getType(), InsertPos);
+ new StoreInst(V, StateMap.AI, false, InsertPos);
+ toErase.push_back(SI);
+ return;
+ }
+
+ if (StateMap.isVector()) {
+ RewriteStoreVector(StateMap, Ref);
+ return;
+ }
+
+ /* This is a non-vector state. Transform the state to the type of Int-N
+ * and use logical shift to extract/insert element data. */
+ ElementInfo Info;
+ getElementInfo(StateMap, Ref, Info);
+
+ Value *V = new LoadInst(StateMap.AI, "", false, InsertPos);
+ V = ConvertType(V, Info.StateTy, InsertPos);
+
+ /* Insert the element. */
+ Data = ConvertType(Data, Info.EltTy, InsertPos);
+ Data = new ZExtInst(Data, Info.StateTy, "", InsertPos);
+
+ if (Info.Shift) {
+ Value *Shift = ConstantInt::get(Data->getType(), Info.Shift * 8);
+ Data = BinaryOperator::Create(Instruction::Shl, Data, Shift, "", InsertPos);
+ }
+
+ unsigned numBits = StateMap.getSize() * 8;
+ unsigned loBit = Info.Shift * 8, hiBit = loBit + Ref.getSize() * 8;
+ APInt mask = ~APInt::getBitsSet(numBits, loBit, hiBit);
+ Value *Mask = ConstantInt::get(Data->getContext(), mask);
+
+ V = BinaryOperator::Create(Instruction::And, V, Mask, "", InsertPos);
+ V = BinaryOperator::Create(Instruction::Or, V, Data, "", InsertPos);
+ V = ConvertType(V, StateMap.getType(), InsertPos);
+
+ new StoreInst(V, StateMap.AI, false, InsertPos);
+ toErase.push_back(SI);
+}
+
+void StateMapper::RewriteLoadVector(StateMapping &StateMap, StateRef &Ref)
+{
+ LoadInst *LI = cast<LoadInst>(Ref.I);
+ Type *Ty = LI->getType();
+ Instruction *InsertPos = LI;
+
+ /* Compute offset, size and element type of this vector operation. */
+ ElementInfo Info;
+ getElementInfo(StateMap, Ref, Info);
+
+ Value *V = new LoadInst(StateMap.AI, "", false, InsertPos);
+ V = ConvertType(V, Info.StateTy, InsertPos);
+
+ /* Extract the element(s) from the vector value. */
+ IntegerType *I32 = IntegerType::get(V->getContext(), 32);
+
+ if (Info.EltTy->isVectorTy()) {
+ /* Multiple elements to load. Use shufflevector. */
+ Value *UndefVal = UndefValue::get(Info.StateTy);
+ SmallVector<Constant*, 8> Indices;
+ for (unsigned i = 0, e = Info.Shift; i != e; ++i)
+ Indices.push_back(ConstantInt::get(I32, Info.Shift + i));
+ Value *CV = ConstantVector::get(Indices);
+ V = new ShuffleVectorInst(V, UndefVal, CV, "", InsertPos);
+ } else {
+ /* Only one element. Use extractelement. */
+ V = ExtractElementInst::Create(V,
+ ConstantInt::get(I32, Info.Shift), "", InsertPos);
+ }
+
+ V = ConvertType(V, Ty, InsertPos);
+
+ LI->replaceAllUsesWith(V);
+ toErase.push_back(LI);
+}
+
+void StateMapper::RewriteStoreVector(StateMapping &StateMap, StateRef &Ref)
+{
+ StoreInst *SI = cast<StoreInst>(Ref.I);
+ Value *Data = SI->getValueOperand();
+ Instruction *InsertPos = SI;
+
+ /* Compute offset, size and element type of this vector operation. */
+ ElementInfo Info;
+ getElementInfo(StateMap, Ref, Info);
+
+ Value *V = new LoadInst(StateMap.AI, "", false, InsertPos);
+ V = ConvertType(V, Info.StateTy, InsertPos);
+ Data = ConvertType(Data, Info.EltTy, InsertPos);
+
+ /* Extract element(s) from data and insert it into the vector value. */
+ IntegerType *I32 = IntegerType::get(V->getContext(), 32);
+
+ if (Info.EltTy->isVectorTy()) {
+ SmallVector<Value *, 8> Partial;
+ for (unsigned i = 0, e = Info.NumElts; i != e; ++i) {
+ Partial.push_back(ExtractElementInst::Create(Data,
+ ConstantInt::get(I32, i), "", InsertPos));
+ }
+ for (unsigned i = 0, e = Info.NumElts; i != e; ++i) {
+ V = InsertElementInst::Create(V, Partial[i],
+ ConstantInt::get(I32, Info.Shift + i), "", InsertPos);
+ }
+ } else {
+ /* Only one element. Use insertelement. */
+ V = InsertElementInst::Create(V, Data,
+ ConstantInt::get(I32, Info.Shift), "", InsertPos);
+ }
+
+ V = ConvertType(V, StateMap.getType(), InsertPos);
+
+ new StoreInst(V, StateMap.AI, false, InsertPos);
+ toErase.push_back(SI);
+}
+
+/* Map state references to the virtual states. */
+void StateMapper::PromoteState(Function &F)
+{
+ /* Pre-load CPU states. */
+ Type *IntPtrTy = DL->getIntPtrType(CPU->getContext());
+ for (auto &StateMap : StateMaps) {
+ if (!StateMap.Addr) {
+ Value *Off = ConstantInt::get(IntPtrTy, StateMap.getStart());
+ Value *GEP = GetElementPtrInst::CreateInBounds(CPU, Off, "",
+ PreCastPos);
+ StateMap.Addr = new BitCastInst(GEP,
+ PointerType::getUnqual(StateMap.getType()), "",
+ PreCastPos);
+ }
+
+ std::string StateName = StateMap.Addr->getName();
+ if (StateName == "")
+ StateName = getStateName(StateMap.getStart());
+ if (StateName == "")
+ StateName = "state";
+ StateName.append(".a");
+
+ StateMap.AI = CreateAlloca(StateMap.getType(), 0, StateName, PreCastPos);
+ CopyState(StateMap.AI, StateMap.Addr, PreLoadPos);
+ }
+
+ /* Rewrite loads and stores. */
+ for (auto &StateMap : StateMaps) {
+ for (auto Ref : StateMap.State->Refs) {
+ if (isa<LoadInst>(Ref->I))
+ RewriteLoad(StateMap, *Ref);
+ else
+ RewriteStore(StateMap, *Ref);
+ }
+ }
+
+ /* Sync CPU states around helper calls. */
+ SyncHelperState();
+
+ /* Post-store dirty values back to CPU states for each exiting block. */
+ for (auto BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
+ BasicBlock *BB = &*BI;
+ if (distance(succ_begin(BB), succ_end(BB)) == 0) /* leaf node */
+ ProcessExitBB(BB);
+ }
+}
+
+/* Determine if the state can be operated as a vector. */
+Type *StateMapper::TryVectorState(StateData &State, Type *Ty)
+{
+ intptr_t StateStart = State.Start;
+ intptr_t StateEnd = State.End;
+ intptr_t StateSize = StateEnd - StateStart;
+
+ /* If the reference type (from the IR) is already a vector type, use it.
+ * Otherwise, query StateType to determine if it is a vector state. */
+ VectorType *VecTy = dyn_cast<VectorType>(Ty);
+ if (!VecTy) {
+ auto TI = --StateType.upper_bound(StateStart);
+ for (; TI != StateType.end() && TI->first < StateEnd; ++TI) {
+ if (TI->second->isVectorTy()) {
+ VecTy = cast<VectorType>(TI->second);
+ break;
+ }
+ }
+ }
+
+ if (!VecTy)
+ return nullptr;
+
+ /* This is a vector state. Now, we need to check whether all state refs can
+ * be composed by the vector element type: (a) the state size is a multiple
+ * of the vector element size, and (b) the size and shift of each state ref
+ * are both a multiple of the vector element size. */
+ Type *ElementTy = VecTy->getScalarType();
+ intptr_t ElementSize = DL->getTypeSizeInBits(ElementTy) / 8;
+ if (StateSize % ElementSize != 0)
+ return nullptr;
+
+ for (auto Ref : State.Refs) {
+ if (Ref->getSize() % ElementSize != 0 ||
+ (Ref->Start - StateStart) % ElementSize != 0)
+ return nullptr;
+ }
+ return VectorType::get(ElementTy, StateSize / ElementSize);
+}
+
+/* Compute state mapping information based on the state mapping rules. */
+void StateMapper::ComputeStateMap(StateMapping &StateMap, StateData &State)
+{
+ /* State mapping rule:
+ * - A guest state is not overlapped: (i.e., same access size)
+ * - Same type: map to this type.
+ * - Different type: select type in the order: vector, float and integer;
+ * use bitcast to convert between different types.
+ * - A guest state is overlapped with other state(s):
+ * - Query StateType to find state size (i.e., boundary) and type:
+ * - Vector type: use insert/extract to manipulate a vector element.
+ * - Other types: use shift to manipulate a sub-register element. */
+ bool sameSize = true;
+ bool hasLoad = false;
+ bool hasStore = false;
+
+ for (auto Ref : State.Refs) {
+ hasLoad |= isa<LoadInst>(Ref->I);
+ hasStore |= isa<StoreInst>(Ref->I);
+ }
+
+ StateRef *Ref = State.Refs.front();
+ Type *Ty = Ref->getType();
+ Value *Addr = getPointerOperand(Ref->I);
+ intptr_t Size = Ref->getSize();
+
+ for (unsigned i = 1, e = State.Refs.size(); i != e; ++i) {
+ StateRef *NextRef = State.Refs[i];
+ Type *NextTy = NextRef->getType();
+ Value *NextAddr = getPointerOperand(NextRef->I);
+
+ /* Check type. */
+ if (Ty != NextTy) {
+ /* Select type in the order: vector, float and integer. */
+ bool Swap = false;
+ if (Ty->isVectorTy() && NextTy->isVectorTy()) {
+ /* We prefer a vector type of small element type. */
+ Type *ATy = cast<VectorType>(Ty)->getScalarType();
+ Type *BTy = cast<VectorType>(NextTy)->getScalarType();
+ if (DL->getTypeSizeInBits(BTy) < DL->getTypeSizeInBits(ATy))
+ Swap = true;
+ } else if (!Ty->isVectorTy() && NextTy->isVectorTy()) {
+ Swap = true;
+ } else if (Ty->isIntegerTy() && NextTy->isFloatTy()) {
+ Swap = true;
+ }
+
+ if (Swap) {
+ std::swap(Ty, NextTy);
+ std::swap(Addr, NextAddr);
+ }
+ }
+
+ /* Check size. */
+ if (Size != NextRef->getSize())
+ sameSize = false;
+ }
+
+ if (sameSize) {
+ /* The same reference size as the state size. */
+ StateMap.Ty = Ty;
+ StateMap.Addr = Addr;
+ } else {
+ /* Different reference sizes. */
+ intptr_t StateSize = State.End - State.Start;
+ Type *VecTy = TryVectorState(State, Ty);
+ StateMap.Ty = VecTy ? VecTy
+ : Type::getIntNTy(Ty->getContext(), StateSize * 8);
+ StateMap.Addr = nullptr;
+ }
+ StateMap.State = &State;
+ StateMap.hasLoad = hasLoad;
+ StateMap.hasStore = hasStore;
+}
+
+/* Analyze instructions in a Function that access CPU states. */
+void StateMapper::AnalyzeState(Function &F)
+{
+ /* Collect instructions (load/store/call) that access CPU states.
+ * Loads/stores that access guest memory or are tagged with volatile
+ * (e.g., accessing the states: %pc and %tcg_exit_req) are ignored. */
+
+ for (auto II = inst_begin(F), EE = inst_end(F); II != EE; ++II) {
+ Instruction *I = &*II;
+ intptr_t Off = 0;
+ if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
+ if (MDFactory::isGuestMemory(I) || LI->isVolatile())
+ continue;
+
+ if (isLegalState(LI->getPointerOperand(), Off))
+ Analyzer.addStateRef(I, Off);
+ } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
+ if (MDFactory::isGuestMemory(I) || SI->isVolatile())
+ continue;
+
+ if (isLegalState(SI->getPointerOperand(), Off))
+ Analyzer.addStateRef(I, Off);
+ } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
+ /* Skip const helper, inlineasm and intrinsic function call. */
+ if (MDFactory::isConst(CI))
+ continue;
+ if (CI->isInlineAsm() || isa<IntrinsicInst>(CI))
+ continue;
+
+ Analyzer.addCall(CI);
+ }
+ }
+
+ /* Ask Analyzer to put state references into groups. */
+ Analyzer.computeState();
+
+ StateList &States = Analyzer.getStateList();
+ if (States.empty())
+ return;
+
+ /* Compute state mapping info. */
+ StateMaps.resize(States.size());
+ for (unsigned i = 0, e = States.size(); i != e; ++i)
+ ComputeStateMap(StateMaps[i], States[i]);
+}
+
+/* Rearrange instructions in the 'init' block. */
+bool StateMapper::init(Function &F)
+{
+ /*
+ * We would like to rearrange the instructions in the 'init' block, in which
+ * gep/cast instructions are in front of other instructions in the block.
+ * For example:
+ * %0 = getelementptr i8* %cpu, i64 0
+ * %1 = bitcast i8* %0 to i32* # gep/cast insns
+ * -------------------------------------- # precast_pos
+ * -------------------------------------- # preload_pos
+ * %2 = load i32, i32* %1 # the other insns
+ * br label %entry
+ */
+ CPU = IF->getDefaultCPU(F);
+ if (!CPU || CPU->getParent() != &F.getEntryBlock())
+ return false;
+
+ Instruction *InsertPos = &*std::next(BasicBlock::iterator(CPU));
+ PreLoadPos = new UnreachableInst(CPU->getContext(), InsertPos);
+ PreCastPos = new UnreachableInst(CPU->getContext(), PreLoadPos);
+
+ toErase.push_back(PreLoadPos);
+ toErase.push_back(PreCastPos);
+
+ /* Move gep/cast instructions. */
+ IVec toMove;
+ BasicBlock *BB = CPU->getParent();
+ for (auto BI = BB->begin(), BE = BB->end(); BI != BE; ++BI) {
+ Instruction *I = &*BI;
+ if (isStatePointer(I))
+ toMove.push_back(I);
+ }
+ for (auto I : toMove)
+ I->moveBefore(PreCastPos);
+
+ return true;
+}
+
+/*
+ * StateMappingPass
+ */
+bool StateMappingPass::runOnFunction(Function &F)
+{
+ return StateMapper(IF).run(F);
+}
+
+char StateMappingPass::ID = 0;
+INITIALIZE_PASS(StateMappingPass, "statemap",
+ "Eliminate redundant loads/stores by mapping CPU states", false, false)
+
+FunctionPass *llvm::createStateMappingPass(IRFactory *IF)
+{
+ return new StateMappingPass(IF);
+}
+
+/*
+ * vim: ts=8 sts=4 sw=4 expandtab
+ */
OpenPOWER on IntegriCloud