   s <- get
   return (ir, s)
 
-translateType :: TypePtr -> KnotMonad Type
-translateType tp = do
+translateType :: KnotState -> TypePtr -> KnotMonad Type
+translateType finalState tp = do
   s <- get
   case M.lookup (ptrToIntPtr tp) (typeMap s) of
     Just t -> return t
-    Nothing -> translateType' tp
-
-{-
-cTypeTag :: TypePtr -> IO TypeTag
-cTypeSize :: TypePtr -> IO Int
-cTypeIsVarArg :: TypePtr -> IO Bool
-cTypeIsPacked :: TypePtr -> IO Bool
-cTypeList :: TypePtr -> IO [TypePtr]
-cTypeInner :: TypePtr -> IO TypePtr
-cTypeName :: TypePtr -> IO String
-cTypeAddrSpace :: TypePtr -> IO Int
--}
-translateType' :: TypePtr -> KnotMonad Type
-translateType' tp = do
+    Nothing -> translateType' finalState tp
+
+translateTypeRec :: KnotState -> TypePtr -> KnotMonad Type
+translateTypeRec finalState tp = do
+  s <- get
+  case M.lookup (ptrToIntPtr tp) (typeMap s) of
+    -- If we already translated, just do the simple thing.
+    Just t -> return t
+    Nothing -> do
+      tag <- liftIO $ cTypeTag tp
+      case tag of
+        -- Break recursive cycles here - just look up the named type in
+        -- the final result.  The outer wrappers will have been
+        -- translated, so this should be sufficient to tie the type knot.
+        TYPE_NAMED -> case M.lookup (ptrToIntPtr tp) (typeMap finalState) of
+          Just t -> return t
+          Nothing -> throw TypeKnotTyingFailure
+        _ -> translateType' finalState tp
+
+translateType' :: KnotState -> TypePtr -> KnotMonad Type
+translateType' finalState tp = do
   s <- get
   tag <- liftIO $ cTypeTag tp
   t <- case tag of

      rtp <- liftIO $ cTypeInner tp
      argTypePtrs <- liftIO $ cTypeList tp

      rType <- translateType rtp
      argTypes <- mapM translateType argTypePtrs

      return $! TypeFunction rType argTypes isVa
    TYPE_STRUCT -> do
      isPacked <- liftIO $ cTypeIsPacked tp
      ptrs <- liftIO $ cTypeList tp

      types <- mapM translateType ptrs

      return $! TypeStruct types isPacked
    TYPE_ARRAY -> do
      sz <- liftIO $ cTypeSize tp
      itp <- liftIO $ cTypeInner tp
      innerType <- translateType itp

      return $! TypeArray sz innerType
    TYPE_POINTER -> do
      itp <- liftIO $ cTypeInner tp
      addrSpc <- liftIO $ cTypeAddrSpace tp
      innerType <- translateType itp

      return $! TypePointer innerType addrSpc
    TYPE_VECTOR -> do
      sz <- liftIO $ cTypeSize tp
      itp <- liftIO $ cTypeInner tp
      innerType <- translateType itp

      return $! TypeVector sz innerType
    TYPE_NAMED -> do
      name <- liftIO $ cTypeName tp
      itp <- liftIO $ cTypeInner tp
      innerType <- translateType itp

      return $! TypeNamed name innerType
  put s { typeMap = M.insert (ptrToIntPtr tp) t (typeMap s) }

                          | InvalidSwitchLayout
                          | InvalidIndirectBranchOperands
                          | KnotTyingFailure
                          | TypeKnotTyingFailure
                          | InvalidSelectArgs !Int
                          | InvalidExtractElementInst !Int
                          | InvalidInsertElementInst !Int
